除了样例全WA求助
查看原帖
除了样例全WA求助
760824
MornStar楼主2024/3/15 13:30

RT,就是官方题解的思路。

#include<bits/stdc++.h>
using namespace std;
const int N=5005,Q=10000005;
const long long INFB=1e16+5,MOD=((1ll<<31)-1);
long long gcd(long long a,long long b){return (b?gcd(b,a%b):a);}
struct fraction{
	int u,d;
	fraction(int _u=0,int _d=1){
		int tmp=gcd(_u,_d);
		_u/=tmp,_d/=tmp;
		u=_u,d=_d;
	}
	friend fraction operator+(fraction a,fraction b){
		long long tmpu=1ll*a.u*b.d+1ll*b.u*a.d,tmpd=1ll*a.d*b.d;
		return fraction(int(tmpu/gcd(tmpu,tmpd)),int(tmpd/gcd(tmpu,tmpd)));
	}
	friend fraction operator+(fraction x,int k){
		long long tmpu=x.u+1ll*k*x.d;
		return fraction(int(tmpu/gcd(tmpu,x.d)),int(x.d/gcd(tmpu,x.d)));
	}
	friend fraction operator*(fraction x,int k){
		long long tmpu=1ll*x.u*k;
		return fraction(int(tmpu/gcd(tmpu,x.d)),int(x.d/gcd(tmpu,x.d)));
	}
	fraction operator-(){return {-u,d};}
	friend bool operator<(fraction x,fraction y){return 1ll*x.u*y.d<1ll*y.u*x.d;}
	friend bool operator<=(fraction x,int y){return x.u<=1ll*y*x.d;}
	friend bool operator>=(fraction x,int y){return x.u>=1ll*y*x.d;}
	friend bool operator<=(fraction x,fraction y){return 1ll*x.u*y.d<=1ll*y.u*x.d;}
};
const fraction INFA={-100000005,1};
struct will_swap{
	short int a,b;fraction t;
	will_swap(short int _a=0,short int _b=0,fraction _t=fraction()){a=_a,b=_b,t=_t;}
}s[N*N];
struct line{
	int k,b,num;
	line(int _k=0,int _b=0,int _num=0){k=_k,b=_b,num=_num;}
	fraction calc(fraction x){return x*k+b;}
}li[N];
struct query{
	int a;long long b;
	query(int _a=0,long long _b=0){a=_a,b=_b;}
}q[Q];
bool cmp_query(query x,query y){return x.a<y.a;}
bool cmp_swap(will_swap x,will_swap y){return x.t<y.t;}
bool cmp_line(line x,line y){return x.calc(INFA)<y.calc(INFA);}
fraction get_swap(line x,line y){
	if(x.k==y.k)	return {100000005,1};
	return fraction((y.b-x.b),(x.k-y.k));
}
int n,m,rnk[N],to[N];
int swap_num,swap_cnt;
long long g_0,ra,rb,ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(short int i=1,x,y;i<=n;i++){
		cin>>x>>y;
		li[i]=line(-x,y,i);
	}
	sort(li+1,li+n+1,cmp_line);
	for(short int i=1;i<=n;i++)	rnk[i]=li[i].num,to[li[i].num]=i;
	for(short int i=1;i<=n;i++){
		for(short int j=i+1;j<=n;j++){
			fraction pos=get_swap(li[i],li[j]);
			if(INFA<=pos)	s[++swap_num]=will_swap(li[i].num,li[j].num,pos);
		}
	}
	stable_sort(s+1,s+swap_num+1,cmp_swap);
	cin>>m>>g_0>>ra>>rb;
	const long long MODA=2*ra+1,MODB=2*rb+1;
	for(int i=1;i<=m;i++){
		int g_1=(48271ll*g_0)%MOD,g_2=(48271ll*g_1)%MOD,g_3=(48271ll*g_2)%MOD;
		//		cerr<<i<<" "<<-ra+g_1%MODA<<" "<<-rb+(g_2*MOD+g_3)%MODB<<"\n";
		q[i]=query(-ra+g_1%MODA,-rb+(g_2*MOD+g_3)%MODB);
		g_0=g_3;
	}
	sort(q+1,q+m+1,cmp_query);
	swap_cnt=1;
	//	for(int i=1;i<=n;i++)	cerr<<rnk[i]<<" ";
	//	cerr<<"\n";
	//	for(int i=1;i<=swap_num;i++)	cerr<<s[i].a<<" "<<s[i].b<<" "<<s[i].t<<"\n";
	//	cerr<<"\n";
	// 	for(int i=1;i<=n;i++)	cerr<<fixed<<setprecision(5)<<li[i].calc(-INFA-0.1)<<"\n";
	// 	cerr<<"\n";
	for(int i=1;i<=m;i++){
		while(s[swap_cnt].t<=q[i].a&&swap_cnt<=swap_num){
			swap(rnk[to[s[swap_cnt].a]],rnk[to[s[swap_cnt].b]]);
			swap(li[to[s[swap_cnt].a]],li[to[s[swap_cnt].b]]);
			swap(to[s[swap_cnt].a],to[s[swap_cnt].b]);
			swap_cnt++;
		}
		//		cerr<<q[i].a<<" "<<"cnt:"<<swap_cnt<<"   ";
		//		for(int j=1;j<=n;j++)	cerr<<rnk[j]<<" ";
		//		cerr<<"\n";
		//		for(int j=1;j<=n;j++)	cerr<<fixed<<setprecision(5)<<li[rnk[to[j]]].calc(q[i].a)<<" "<<li[rnk[to[j]]].num<<"\n";
		//		cerr<<"\n";
		short int l=1,r=n;
		while(l<r){
			short int mid=(l+r+1)>>1;
			if(li[rnk[to[mid]]].calc(q[i].a)>=q[i].b)	r=mid-1;
			else	l=mid;
		}
		//		cerr<<q[i].a<<" "<<q[i].b<<" "<<i<<" "<<l<<"\n";
		ans+=n-l;
	}
	cout<<ans<<"\n";
}
2024/3/15 13:30
加载中...