【随机化】Petrozavodsk Summer Training Camp 2016 Day 5: Petr Mitrichev Contest 14, Saturday, August 27, 2016 Problem I. Vier

给你一个1~n的排列，让你找出4个下标a b c d，满足

（a+b）%n=（c+d）%n

（w(a)+w(b)）%n=（w(c)+w(d)）%n，并且是非平凡解。

发现对于每个数i，找出两个数和为其的数量大概是O（n），于是可以随机找，压到vector里存下，直到找到一个解为止。

#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
int n,a[1000010];
vector<int>b[1000010],c[1000010];
int main(){
	freopen("vier.in","r",stdin);
	freopen("vier.out","w",stdout);
	srand(233);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	while(1){
		int A=rand()%n+1;
		int B=rand()%n+1;
		int t=(A+B+a[A]+a[B])%n;
		for(int i=0;i<b[t].size();++i){
			if((A+B)%n==(b[t][i]+c[t][i])%n && (a[A]+a[B])%n==(a[b[t][i]]+a[c[t][i]])%n && !(A==b[t][i] && B==c[t][i]) && !(A==c[t][i] && B==b[t][i])){
				puts("Ja");
				printf("%d %d %d %d
",A,B,b[t][i],c[t][i]);
				return 0;
			}
		}
		b[t].push_back(A);
		c[t].push_back(B);
	}
	return 0;
}