萌新刚学OI,0pts请求DEBUG
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/7/9 09:30
#include<algorithm>
#include<cstdio>
#include<set>
#define int long long
#define base 1000000007
struct node{
	int answer,seat;
};
int data[200002],hash[200002],hash1[200002],hash2[200002];
node chart[300003];
int result,count;
std::set<int> set;
inline bool compare(const node &first,const node &second){
	if(first.answer==second.answer){
		return first.seat<second.seat;
	};
	return first.answer>second.answer;
};
signed main(signed argc,char **argv){
	int size;
	scanf("%lld",&size);
	for(int iter=1;iter<=size;++iter){
		scanf("%lld",&data[iter]);
	};
	hash[0]=1;
	for(int iter=1;iter<=size;++iter){
		hash[iter]=hash[iter-1]*base;
	};
	for(int iter=1;iter<=size;++iter){
		hash1[iter]=hash1[iter-1]*base+data[iter];
	};
	for(int iter=size;iter>=1;--iter){
		hash2[iter]=hash2[iter+1]*base+data[iter];
	};
	int memory=size;
	for(int first=1;first<=memory;++first){
		int result=0;
		for(int second=first;second<=size;second+=first){
			int worth=(hash1[second]-hash1[second-first]*hash[first])*(hash2[second-first+1]-hash1[second+1]*hash[first]);
			if(set.insert(worth).second){
				++result;
			};
		};
		if(result){
			memory=std::min(memory,size/result);
			chart[++count].answer=result;
			chart[count].seat=first;
		};
	};
	std::sort(chart+1,chart+1+count,compare);
	int iter;
	for(iter=2;iter<=count;++iter){
		if(chart[iter].answer!=chart[iter-1].answer){
			break;
		};
	};
	printf("%lld %lld\n",chart[1].answer,iter-1);
	while(--iter){
		printf("%lld ",chart[iter].seat);
	};
	return 0;
};
2024/7/9 09:30
加载中...