QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #321307 | #8216. Jumbled Primes | ucup-team052 | AC ✓ | 568ms | 3820kb | C++23 | 5.0kb | 2024-02-04 13:25:27 | 2024-02-04 13:25:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rnd(1);
inline int Rnd(int l,int r) {return rnd()%(r-l+1)+l;}
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 105
int a[N],n=100;
int cache[N][N],prime[N],qcnt;
int query(int x,int y)
{
assert(x!=y);
if(x>y) swap(x,y);
if(cache[x][y]) return cache[x][y];
qcnt++;
#ifdef wasa855
return cache[x][y]=__gcd(a[x],a[y]);
#endif
printf("? %d %d\n",x,y);
fflush(stdout);
return cache[x][y]=read();
}
int sm[N],vis[N];
void solve(int w,vector<int> v)
{
}
void work()
{
#ifdef wasa855
for(int i=1;i<=n;i++) a[i]=i;
shuffle(a+1,a+n+1,rnd);
#endif
memset(cache,0,sizeof(cache));
memset(vis,0,sizeof(vis));
memset(sm,0,sizeof(sm));
pair<int,int> q2,q3,q5,q7,q4,q9; int _vis=0;
while(_vis<31)
{
int x=Rnd(1,n),y=Rnd(1,n);
if(x==y) continue;
int w=query(x,y);
if(w%2==0) _vis|=1,q2={x,y};
if(w%3==0) _vis|=2,q3={x,y};
if(w%5==0) _vis|=4,q5={x,y};
if(w%7==0) _vis|=8,q7={x,y};
if(w%4==0) _vis|=16,q4={x,y};
if(w%9==0) q9={x,y};
}
// return ;
for(int i=1;i<=n;i++)
{
if(i==q2.first||i==q2.second) {sm[i]=2; continue;}
if(query(q2.first,i)%2==0) sm[i]=2;
}
for(int i=1;i<=n;i++)
{
if(sm[i]) continue;
if(i==q3.first||i==q3.second) {sm[i]=3; continue;}
if(query(q3.first,i)%3==0) sm[i]=3;
}
for(int i=1;i<=n;i++)
{
if(sm[i]) continue;
if(i==q5.first||i==q5.second) {sm[i]=5; continue;}
if(query(q5.first,i)%5==0) sm[i]=5;
}
for(int i=1;i<=n;i++)
{
if(sm[i]) continue;
if(i==q7.first||i==q7.second) {sm[i]=7; continue;}
if(query(q7.first,i)%7==0) sm[i]=7;
}
// for(int i=1;i<=n;i++) if(!sm[i]) printf("%d ",prime[a[i]]);
// int c7=0; for(int i=1;i<=n;i++) if(sm[i]==7) c7++;
// cout<<c7<<endl;
vector<int> pw2,t7;
for(int i=1;i<=n;i++) if(sm[i]==2)
{
if(i==q4.first||i==q4.second||query(i,q4.first)%4==0) continue;
if(i==q3.first||i==q3.second||query(i,q3.first)%3==0) continue;
if(i==q5.first||i==q5.second||query(i,q5.first)%5==0) continue;
if(i==q7.first||i==q7.second||query(i,q7.first)%7==0)
{
t7.push_back(i);
continue;
}
int ok=1;
for(int j=1;j<=n;j++) if(sm[j]==0&&vis[j]==0)
{
if(query(i,j)!=1)
{
ok=0,vis[j]=2;
break;
}
}
if(ok) pw2.push_back(i);
}
assert(pw2.size()==1);
sm[pw2[0]]=0;
while(q9.first==0)
{
int x=Rnd(1,n),y=Rnd(1,n);
if(x==y||(sm[x]!=2&&sm[x]!=3)||(sm[y]!=2&&sm[y]!=3)) continue;
int w=query(x,y);
if(w%9==0) q9={x,y};
}
vector<int> pw3,t5;
for(int i=1;i<=n;i++) if(sm[i]==3)
{
if(i==q9.first||i==q9.second||query(i,q9.first)%9==0) continue;
if(i==q5.first||i==q5.second||query(i,q5.first)%5==0)
{
t5.push_back(i);
continue;
}
if(i==q7.first||i==q7.second||query(i,q7.first)%7==0) continue;
int ok=1;
for(int j=1;j<=n;j++) if(sm[j]==0&&vis[j]==2)
{
if(query(i,j)!=1)
{
ok=0,vis[j]=3;
break;
}
}
if(ok) pw3.push_back(i);
}
// for(int i:t5) printf("%d ",a[i]);
// cout<<"\n";
assert(pw3.size()==1);
sm[pw3[0]]=0;
vector<int> pw5; int tcnt=0;
for(int i=1;i<=n;i++) if(sm[i]==5)
{
if(i==q7.first||i==q7.second||query(i,q7.first)%7==0) continue;
int ok=1;
for(int j=1;j<=n;j++) if(sm[j]==0&&vis[j]==3)
{
if(query(i,j)!=1)
{
ok=0,vis[j]=5;
break;
}
}
if(ok)
{
tcnt++;
if(tcnt==2)
{
if(pw5.empty()) pw5.push_back(i);
continue;
}
for(int j:t5)
{
if(query(i,j)==25)
{
ok=0;
break;
}
}
if(ok) pw5.push_back(i);
}
}
assert(pw5.size()==1);
sm[pw5[0]]=0;
vector<int> pw7; tcnt=0;
for(int i=1;i<=n;i++) if(sm[i]==7)
{
int ok=1;
for(int j=1;j<=n;j++) if(sm[j]==0&&vis[j]==5)
{
if(query(i,j)!=1)
{
ok=0,vis[j]=7;
break;
}
}
if(ok)
{
tcnt++;
if(tcnt==2)
{
if(pw7.empty()) pw7.push_back(i);
continue;
}
for(int j:t7)
{
if(query(i,j)==49)
{
ok=0;
break;
}
}
if(ok) pw7.push_back(i);
}
}
assert(pw7.size()==1);
sm[pw7[0]]=0;
#ifdef wasa855
for(int i=1;i<=n;i++)
{
// printf("%d %d - %d\n",sm[i],a[i],prime[a[i]]);
if(sm[i]==0)
{
if(prime[a[i]]!=1) exit(0);
}
else
{
if(prime[a[i]]!=0) exit(0);
}
}
#else
printf("! ");
for(int i=1;i<=n;i++) printf("%d",!sm[i]);
cout<<endl;
#endif
}
signed main()
{
for(int i=1;i<=n;i++)
{
int ok=1;
for(int j=2;j*j<=i;j++) if(i%j==0) ok=0;
prime[i]=ok;
}
int T=1000; while(T--) work();
cerr<<qcnt<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 568ms
memory: 3820kb
input:
1 1 1 1 1 18 1 1 5 1 2 1 3 4 4 1 1 1 2 1 1 49 13 1 1 1 2 1 1 1 2 2 2 1 2 1 2 2 2 2 2 1 1 1 2 2 1 1 1 1 1 13 1 1 2 1 2 2 2 1 1 1 2 2 2 1 2 2 2 1 1 1 2 1 1 1 2 2 2 1 2 1 1 2 2 2 1 1 1 2 2 2 2 2 2 1 2 13 1 1 2 1 2 1 2 26 1 2 26 2 1 13 2 2 1 2 1 1 2 3 1 1 1 9 1 1 1 3 1 9 1 3 3 1 1 1 3 1 9 1 3 1 1 1 1 1 ...
output:
? 42 55 ? 7 16 ? 1 39 ? 24 97 ? 59 80 ? 38 81 ? 8 70 ? 5 35 ? 13 84 ? 41 79 ? 94 99 ? 42 45 ? 83 87 ? 18 65 ? 43 83 ? 5 6 ? 73 84 ? 28 100 ? 6 100 ? 17 50 ? 71 82 ? 70 97 ? 1 6 ? 2 6 ? 3 6 ? 4 6 ? 6 7 ? 6 8 ? 6 9 ? 6 10 ? 6 11 ? 6 12 ? 6 13 ? 6 14 ? 6 15 ? 6 16 ? 6 17 ? 6 18 ? 6 19 ? 6 20 ? 6 21 ? 6...
result:
ok Primes are found successfully with S = 566034 queries total