QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344520 | #8216. Jumbled Primes | Crysfly# | AC ✓ | 775ms | 3748kb | C++17 | 3.5kb | 2024-03-04 18:23:03 | 2024-03-04 18:23:05 |
Judging History
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