QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471184#8216. Jumbled PrimesPhantomThresholdAC ✓766ms3912kbC++175.5kb2024-07-10 19:08:122024-07-10 19:08:12

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 19:08:12]
  • 评测
  • 测评结果:AC
  • 用时:766ms
  • 内存:3912kb
  • [2024-07-10 19:08:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int __CNT=0;
int __totCNT=0;

//#define DEBUG

#ifdef DEBUG
int ha[105];
#endif

#ifdef DEBUG
mt19937 rng_ha((unsigned long long)(new char));
void prepare_ha(){
	for (int i=1;i<=100;i++) ha[i]=i;
	shuffle(ha+1,ha+100+1,rng_ha);	
}
#endif

int real_ask(int i,int j){
	__CNT++;
	cout << "? " << i << " " << j << endl;
	
	int ret=0;
	#ifdef DEBUG
		ret=__gcd(ha[i],ha[j]);
	#else
	cin >> ret;
	#endif
	return ret;	
}

int rec[105][105];
int disc[105];
int notp[105];

void upd(int i,int g){
	int _gg=__gcd(disc[i],g);
	disc[i]=disc[i]*g/_gg;
}
int ask(int i,int j){
	assert(i!=j);
	if (i>j) swap(i,j);
	if (rec[i][j]!=0) return rec[i][j];
	rec[i][j]=real_ask(i,j);
	upd(i,rec[i][j]);
	upd(j,rec[i][j]);
	return rec[i][j];
}

void answer(const vector<int> &ans){
	cout << "! ";
	for (int i=1;i<=100;i++) cout << ans[i];
	cout << endl;
	#ifdef DEBUG
	for (int i=1;i<=100;i++) assert(notp[ha[i]]!=ans[i]);
	#endif
}


//mt19937 rng((unsigned long long)(new char));
mt19937 rng(58);
pair<vector<int>,vector<int>> fliter(const vector<int> &v,int k,int qingding=0){
	int pos=qingding;
	int sz=v.size();
	while (!pos){
		for (int i=1;i<=100;i++) if (disc[i]%k==0){pos=i;break;}
		if (pos!=0) break;
		int x=rng()%sz;
		int y=rng()%sz;
		while (y==x) y=rng()%sz;
		ask(v[x],v[y]);
	}
//	cerr << "pos,disc[pos],ha[pos] : " << pos << " " << disc[pos] << " " << ha[pos] << endl;
	vector<int> vk;
	vector<int> vnotk;
	for (auto x:v){
		int tmp=0;
		if (x!=pos) tmp=ask(x,pos);
		else tmp=disc[x];
		if (tmp%k==0) vk.push_back(x);
		else vnotk.push_back(x);
	}
	return make_pair(vk,vnotk);
}
void solve(){
	vector<int> ans(105);
	for (int i=1;i<=100;i++){
		for (int j=1;j<=100;j++){
			rec[i][j]=0;
		}
	}
	for (int i=1;i<=100;i++) disc[i]=1;
	
	vector<int> v;
	for (int i=1;i<=100;i++) v.push_back(i);
	
	int pos6=0;
	int pos5=0;
	int pos7=0;
	{
		while (1){
			for (int i=1;i<=100;i++){
				if (disc[i]%6==0){
					pos6=i;
				}
				if (disc[i]%5==0){
					pos5=i;	
				}
				if (disc[i]%7==0){
					pos7=i;	
				}
			}
			if (pos6!=0 && pos5!=0 && pos7!=0) break;
			int x=rng()%100;
			int y=rng()%100;
			while (y==x) y=rng()%100;
			ask(v[x],v[y]);
		}
	}
	
	auto [v2,vnot2]=fliter(v,2,pos6);
	auto [v4,v2not4]=fliter(v2,4);
	
	#ifdef DEBUG
	cerr << "stage 1 : " << __CNT << endl;
	#endif
	
	vector<int> v3,vnot23;
	for (auto x:vnot2){
		if (disc[x]%3==0) v3.push_back(x);
		else vnot23.push_back(x);
	}
	
	auto [v5,vnot235]=fliter(vnot23,5,pos5);
	auto [v7,vnot2357]=fliter(vnot235,7,pos7);
	
	#ifdef DEBUG
	cerr << "stage 2 : " << __CNT << endl;
	#endif
	
	vector<int> v2rest=v2not4;
	{
		{
			auto [_1,_2]=fliter(v2rest,3,pos6);
			swap(_2,v2rest);
		}
		{
			auto [_1,_2]=fliter(v2rest,5,pos5);
			swap(_2,v2rest);
		}
		{
			auto [_1,_2]=fliter(v2rest,7,pos7);
			swap(_2,v2rest);
		}
	}
	
	#ifdef DEBUG
	cerr << "stage 3 : " << __CNT << endl;
	#endif
	vector<int> v3rest=v3;
	{
		{
			auto [_1,_2]=fliter(v3rest,9);
			swap(_2,v3rest);
		}
		{
			auto [_1,_2]=fliter(v3rest,5,pos5);
			swap(_2,v3rest);
		}
		{
			auto [_1,_2]=fliter(v3rest,7,pos7);
			swap(_2,v3rest);
		}
	}
	#ifdef DEBUG
	cerr << "stage 4 : " << __CNT << endl;
	#endif
	vector<int> v5rest=v5;
	{
		{
			auto [_1,_2]=fliter(v5rest,7,pos7);
			swap(_2,v5rest);
		}	
	}
	#ifdef DEBUG
	cerr << "stage 5 : " << __CNT << endl;
	#endif
	
	{
		vector<int> vis(105);
		for (auto x:v2rest){
			if (vis[x]) continue;
			for (auto y:v3rest){
				if (vis[y]) continue;
				if (x!=y){
					int tmp=ask(x,y);
					if (tmp!=1){
						vis[x]=1;
						vis[y]=1;
						break;
					}
				}
			}
		}
	}
	#ifdef DEBUG
	cerr << "stage 6 : " << __CNT << endl;
	#endif
	for (auto x:v3rest){
		for (auto y:v5rest){
			if (x!=y) ask(x,y);
		}
	}
	#ifdef DEBUG
	cerr << "stage 7 : " << __CNT << endl;
	#endif
	for (auto x:v5rest){
		for (auto y:v7){
			if (x!=y) ask(x,y);
		}
	}
	#ifdef DEBUG
	cerr << "stage 8 : " << __CNT << endl;
	#endif
	{
		vector<int> v35;
		for (int i=1;i<=100;i++) if (disc[i]%15==0) v35.push_back(i);
		vector<int> v5only;
		for (int i=1;i<=100;i++) if (disc[i]==5) v5only.push_back(i);
		for (auto x:v5only){
			for (auto y:v35){
				if (x!=y) ask(x,y);
			}
		}
	}
	#ifdef DEBUG
	cerr << "stage 9 : " << __CNT << endl;
	#endif
	{
		vector<int> v27;
		for (int i=1;i<=100;i++) if (disc[i]%14==0) v27.push_back(i);
		vector<int> v7only;
		for (int i=1;i<=100;i++) if (disc[i]==7) v7only.push_back(i);
		for (auto x:v7only){
			for (auto y:v27){
				if (x!=y) ask(x,y);
			}
		}
	}
	#ifdef DEBUG
	cerr << "stage 10 : " << __CNT << endl;
	#endif
	{
		vector<int> v2only;
		for (int i=1;i<=100;i++) if (disc[i]==2) v2only.push_back(i);
		
		for (auto x:v2only){
			for (auto y:vnot2357){
				if (x!=y) ask(x,y);
			}
		}
	}
	#ifdef DEBUG
	cerr << "stage 11 : " << __CNT << endl;
	#endif
	for (int i=1;i<=100;i++) if (disc[i]==1 || !notp[disc[i]]) ans[i]=1;
	answer(ans);
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	notp[1]=0;
	for (int i=2;i<=100;i++){
		for (int j=i+i;j<=100;j+=i) notp[j]=1;
	}
	
	int Tcase=1000;
	for (int ttt=1;ttt<=Tcase;ttt++){
		#ifdef DEBUG
			prepare_ha();
		#endif
		__CNT=0;
		solve();
		__totCNT+=__CNT;
		cerr << "turn , cnt , totcnt: " << ttt << " " << __CNT << " " << __totCNT << endl;
	//	assert(__totCNT<=1000*600);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 766ms
memory: 3912kb

input:

1
9
1
1
26
1
2
1
1
1
1
3
2
3
1
2
1
1
1
2
1
1
4
1
1
1
1
2
1
1
1
1
6
4
8
1
1
6
3
1
1
3
2
1
2
2
2
1
1
1
1
1
1
1
7
3
1
1
5
3
1
1
1
3
2
2
1
1
1
2
16
3
2
1
12
4
4
16
12
3
1
3
2
24
3
1
1
1
3
1
3
1
8
3
2
24
2
1
1
1
4
16
2
1
6
6
4
1
1
1
6
3
1
3
2
2
4
1
4
3
1
12
4
3
1
3
2
8
2
2
16
8
1
2
1
1
1
6
3
48
1
6
4
3
2...

output:

? 16 73
? 48 54
? 50 59
? 61 76
? 6 86
? 3 82
? 25 47
? 41 85
? 59 67
? 41 95
? 9 100
? 36 83
? 13 25
? 38 69
? 15 98
? 15 18
? 64 97
? 36 37
? 3 62
? 11 44
? 5 11
? 28 59
? 20 65
? 16 78
? 12 16
? 59 79
? 8 40
? 58 94
? 70 79
? 1 19
? 20 54
? 47 50
? 38 53
? 49 75
? 64 90
? 18 30
? 25 68
? 13 64
? ...

result:

ok Primes are found successfully with S = 567810 queries total