QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344520#8216. Jumbled PrimesCrysfly#AC ✓775ms3748kbC++173.5kb2024-03-04 18:23:032024-03-04 18:23:05

Judging History

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

  • [2024-03-04 18:23:05]
  • 评测
  • 测评结果:AC
  • 用时:775ms
  • 内存:3748kb
  • [2024-03-04 18:23:03]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 105
#define inf 0x3f3f3f3f

int n;
mt19937_64 rnd(time(0));

int per[maxn];
int mp[maxn][maxn],cnt;
int Q(int a,int b){
	if(a==b){
		exit(0);
	}
	if(mp[a][b]!=-1)return mp[a][b];
	++cnt;
	if(cnt>600*1000){
		exit(0);
	}
//	return __gcd(per[a],per[b]);
	cout<<"? "<<a<<" "<<b<<endl;
	assert(cin>>mp[a][b]);
	mp[b][a]=mp[a][b]; return mp[a][b];
}

int p[7]={1,2,3,5,7};
int id[7];

int up[maxn];
int ask(int a,int b){
	int x=Q(a,b);
	up[a]=up[a]*x/__gcd(x,up[a]);
	up[b]=up[b]*x/__gcd(x,up[b]);
	return x;
}
vi buc[7];
bool res[maxn];

vi o1={0, 4,  9,   25,49};
vi oo={0,2*21,3*10,15,14};
vi ps={0, 1,  2,  3 , 6};
int id2[6];

void find2(){
	For(i,1,4){
		id2[i]=0;
		For(j,1,n) if(up[j]%o1[i]==0) id2[i]=j;
	//	cerr<<"id2 "<<o1[i]<<" "<<id2[i]<<" "<<per[id2[i]]<<"\n";
	}
}

void work()
{
	n=100;
	//cnt=0;
	For(i,1,n)For(j,1,n)mp[i][j]=-1;
	
	For(i,1,n)up[i]=1,res[i]=0;
	For(i,0,4)buc[i].clear();
	For(i,0,4)id[i]=id2[i]=0;
	
	For(i,1,n)per[i]=i; shuffle(per+1,per+n+1,rnd);
	For(i,1,4){
		id[i]=0;
		For(j,1,n)if(up[j]%p[i]==0)id[i]=j;
		if(!id[i]){
			while(!id[i]){
				int u=rnd()%n+1;
				int v=rnd()%n+1;
				while(v==u)v=rnd()%n+1;
				ask(u,v);
				if(up[u]%p[i]==0)id[i]=u;
			}
		}
		For(j,1,n)if(j!=id[i]){
			ask(id[i],j);
		}
		For(j,1,n)if(up[j]==p[i])buc[i].pb(j);
		shuffle(ALL(buc[i]),rnd);
	}
	For(i,1,n) if(__gcd(up[i],2*3*5*7ll)==1) res[i]=1;
//	cerr<<"cnt "<<cnt<<"\n";
	
	find2();
	
	Rep(i,4,1){
	//	cout<<"sz "<<buc[i].size()<<"\n";
		
		for(int x:buc[i]){
			bool is=1;
			
			if(up[x]!=p[i]) is=0;
			
			vi o;
		For(j,1,n)
			if(__gcd(up[j],2*3*5*7ll*2*3*5*7ll)==ps[i])o.pb(j);
		shuffle(ALL(o),rnd);
			
		
			
			if(is){
				if(id2[i]){
					if(x!=id2[i]) ask(x,id2[i]);
					else is=0;
				}else{
				//	cout<<"qwq "<<i<<"\n";
				//	cout<<"x: "<<per[x]<<"\n";
					find2();
					For(j,1,n){
					//	cout<<"j: "<<j<<" "<<per[j]<<" "<<up[j]<<" "<<__gcd(up[j],oo[i])<<"\n";
						if(__gcd(up[j],oo[i])==oo[i] && j!=x){
						//	cout<<"Ask "<<per[j]<<"\n";
							ask(x,j);
							if(up[x]!=p[i]){
								is=0;
								break;
							}
							if(up[j]%o1[i]==0){
								break;
							}
						}
					}
				}
				if(up[x]!=p[i]) is=0;
			}
			
			if(is){
				for(int y:o){
					ask(x,y);
					if(up[x]!=p[i]){
						is=0;
						break;
					}
				}
			}
			
			if(is){
				res[x]=1;
		//		cout<<"find: "<<x<<" "<<per[x]<<"\n";
	//			assert(per[x]==p[i]);
	//			for(int y:o) cout<<"y: "<<per[y]<<"\n";
				break;
			}
		}
	}
//	cerr<<"cnts "<<cnt<<"\n";
	cout<<"! ";For(i,1,n)cout<<res[i];cout<<endl;
}

signed main()
{
	int T=1000;
	while(T--)work();
	//cerr<<"cntall "<<cnt<<"\n";
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 775ms
memory: 3748kb

input:

1
1
1
2
1
1
1
1
1
2
2
1
1
1
2
4
2
1
2
1
4
4
4
4
4
1
1
1
2
4
1
1
1
1
1
1
1
1
4
1
2
4
2
1
23
1
4
4
2
1
2
2
4
1
1
1
2
1
1
23
2
4
1
1
1
4
4
4
1
1
1
2
4
2
2
4
4
1
2
1
1
1
2
1
4
1
2
4
1
2
2
4
1
1
2
2
1
4
1
1
4
46
1
4
1
1
1
1
1
9
3
1
1
1
27
1
1
1
1
1
1
1
9
3
1
1
3
1
1
1
3
1
3
1
3
3
1
1
1
3
1
9
1
1
3
1
9
1
...

output:

? 55 49
? 76 42
? 29 51
? 61 58
? 61 1
? 61 2
? 61 3
? 61 4
? 61 5
? 61 6
? 61 7
? 61 8
? 61 9
? 61 10
? 61 11
? 61 12
? 61 13
? 61 14
? 61 15
? 61 16
? 61 17
? 61 18
? 61 19
? 61 20
? 61 21
? 61 22
? 61 23
? 61 24
? 61 25
? 61 26
? 61 27
? 61 28
? 61 29
? 61 30
? 61 31
? 61 32
? 61 33
? 61 34
? 61 ...

result:

ok Primes are found successfully with S = 559241 queries total