QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #321312 | #8216. Jumbled Primes | ucup-team052 | AC ✓ | 551ms | 3864kb | C++23 | 5.0kb | 2024-02-04 13:32:27 | 2024-02-04 13:32:28 |
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 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,q6,q7,q4,q9; int _vis=0;
while(_vis<63)
{
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%6==0) _vis|=32,q6={x,y};
if(w%9==0) q9={x,y};
}
q2=q6,q3=q6;
// return ;
for(int i=1;i<=n;i++)
{
if(i==q2.first||i==q2.second) {sm[i]=2; continue;}
if(query(q6.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(q6.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==q3.first||i==q3.second||query(i,q3.first)%3==0) continue;
if(i==q4.first||i==q4.second||query(i,q4.first)%4==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: 551ms
memory: 3864kb
input:
1 1 1 1 2 4 1 1 1 1 1 3 3 1 1 1 1 1 1 2 7 8 1 2 2 4 2 1 35 1 2 1 3 2 1 1 1 10 1 1 1 4 3 1 1 2 1 1 1 2 4 4 4 1 1 1 4 1 1 1 1 3 3 1 1 2 2 2 1 2 1 2 3 2 3 1 1 17 1 1 1 1 3 1 1 5 13 1 1 4 1 1 1 1 1 1 8 1 1 2 1 1 1 2 1 1 2 4 1 1 4 2 3 2 5 2 1 1 1 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 7 1 2 1 1 1 1 1 1 5 ...
output:
? 8 51 ? 9 67 ? 23 56 ? 24 98 ? 6 35 ? 61 86 ? 2 16 ? 8 55 ? 52 68 ? 9 11 ? 52 90 ? 1 22 ? 17 24 ? 23 90 ? 16 89 ? 2 32 ? 24 86 ? 2 27 ? 2 18 ? 39 93 ? 55 58 ? 20 75 ? 22 37 ? 7 94 ? 39 83 ? 71 96 ? 25 66 ? 8 18 ? 51 58 ? 62 66 ? 7 93 ? 17 68 ? 67 69 ? 13 86 ? 47 92 ? 1 61 ? 22 43 ? 7 21 ? 29 30 ? 1...
result:
ok Primes are found successfully with S = 526632 queries total