QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #331633 | #8216. Jumbled Primes | ucup-team2303 | AC ✓ | 712ms | 24476kb | C++14 | 4.3kb | 2024-02-18 16:08:53 | 2024-02-18 16:08:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,st[1000001],u[1000001],vi[1000001],g[1000001],st1[1000001],cn1,cn2,st2[1000001],vv[1000001];
struct p{long long q,w;}l[1000001];
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long ask(long long qq,long long ww)
{
++an;
printf("? %lld %lld\n",qq,ww);
fflush(stdout);
scanf("%lld",&q);
fflush(stdout);
return q;
// return gcd(d[qq],d[ww]);
}
void ch(long long qq)
{
if(!h[g[qq]]) vi[qq]=1;
}
void ins(long long qq,long long ww)
{
g[qq]=g[qq]*ww/gcd(g[qq],ww);
}
int main()
{
h[1]=1;
for(int i=2;i<=100;i++)
{
h[i]=1;
for(int j=2;j*j<=i;j++)
{
if(i%j==0) h[i]=0;
}
if(h[i]) st[++cn]=i;
}st[0]=1;
// cout<<cn;return 0;
for(int ii=1;ii<=1000;ii++)
{
a=100;
for(int i=1;i<=a;i++) d[i]=i;
random_shuffle(d+1,d+a+1);
long long hh=1;
for(int i=1;i<=a;i++) v[i]=vi[i]=0,g[i]=1;
for(int i=1;i<=a;i++) u[i]=0;
for(int k=1;k<=4;k++)
{
long long idd=0;
cn1=0;
for(int i=1;i<=a;i++)
{
if(g[i]%st[k]==0)
{
idd=i;break;
}
if(g[i]*st[k]<=a) st1[++cn1]=i;
}
while(1)
{
if(idd) break;
long long t1=rnd()%cn1+1,t2=rnd()%cn1+1;
while(t1==t2) t2=rnd()%cn1+1;
long long ff=ask(st1[t1],st1[t2]);
if(ff%st[k]==0)
{
idd=st1[t1];break;
}
if(ff%st[k]==0)
{
idd=st1[t2];break;
}
}
for(int i=1;i<=a;i++) ch(i);
for(int i=1;i<=a;i++)
{
if(!vi[i]&&g[i]*st[k]<=a&&i!=idd)
{
long long ff=ask(idd,i);
ins(i,ff);ins(idd,ff);
}
}
for(int i=1;i<=a;i++) ch(i);
}
for(int k=1;k<=4;k++)
{
cn1=0;
for(int i=1;i<=a;i++)
{
if(g[i]%st[k]==0)
{
if(g[i]*st[k]<=a) st1[++cn1]=i;
}
}
long long idd=0;
for(int i=1;i<=a;i++)
{
if(g[i]%(st[k]*st[k])==0)
{
idd=i;break;
}
}
while(1)
{
if(idd) break;
long long t1=rnd()%cn1+1,t2=rnd()%cn1+1;
while(t1==t2) t2=rnd()%cn1+1;
long long ff=ask(st1[t1],st1[t2]);
ins(st1[t1],ff);
ins(st1[t2],ff);
if(g[st1[t1]]%(st[k]*st[k])==0)
{
idd=st1[t1];break;
}
if(g[st1[t2]]%(st[k]*st[k])==0)
{
idd=st1[t2];break;
}
}
for(int i=1;i<=cn1;i++)
{
if(st1[i]!=idd&&!vi[st1[i]]&&g[st1[i]]*st[k]<=a)
{
long long ff=ask(st1[i],idd);
ins(st1[i],ff);
ins(idd,ff);
}
}
for(int i=1;i<=a;i++) ch(i);
}
for(int i=1;i<=a;i++) ch(i);
for(int i=4;i>=1;i--)
{
cn1=cn2=0;
for(int j=1;j<=a;j++)
{
if(!vi[j]&&g[j]%st[i]==0)
{
st1[++cn1]=j;
}
}
if(i==1)
{
for(int j=1;j<=a;j++)
{
if(!vi[j]&&g[j]==1) st2[++cn2]=j;
}
}
else
{
for(int j=1;j<=a;j++)
{
if(!vi[j]&&g[j]%st[i]!=0&&g[j]!=1&&g[j]<=7)
{
st2[++cn2]=j;
}
if(vi[j]&&g[j]%st[i-1]==0&&h[g[j]/st[i-1]]&&(g[j]/st[i-1])*st[i]<=a&&(g[j]/st[i-1])*st[i+1]>a)
{
st2[++cn2]=j;
}
}
}
for(int j=1;j<=a;j++) vv[j]=0;
for(int j=1;j<=cn1;j++)
{
for(int k=1;k<=cn2;k++)
{
if(vv[st2[k]]) continue;
if(vi[st1[j]]&&vi[st2[k]]) continue;
if(vi[st1[j]])
{
long long hh=g[st1[j]]/st[i],fl=1;
for(int ll=1;ll<=a;ll++)
{
if(g[ll]==hh*g[st2[k]]) fl=0;
}
if(!fl) continue;
}
long long ff=ask(st1[j],st2[k]);
ins(st1[j],ff);
ins(st2[k],ff);
ch(st1[j]);
}
for(int k=1;k<=a;k++)
{
if(!vi[k]&&!h[g[k]]) vv[k]=1;
ch(k);
}
}
}
printf("! ");
fflush(stdout);
for(int i=1;i<=a;i++)
{
if(!vi[i]) printf("1");
else printf("0");
}
printf("\n");
fflush(stdout);
// for(int i=1;i<=a;i++)
// {
// if(!vi[i])
// {
// if(!h[d[i]])
// {
// cout<<g[i]<<" ";
// for(int j=1;j<=a;j++)
// {
// if(d[j]==31)
// {
// cout<<g[j]<<" ";
// }
// }
// cout<<d[i];return 0;
// }
// }
// }
// cout<<ii<<"\n";
// for(int i=1;i<=a;i++)
// {
// if(!vi[i]) cout<<d[i]<<" ";
// }return 0;
}
// printf("%lld",an);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 712ms
memory: 24476kb
input:
1 2 1 1 1 1 1 2 2 1 1 19 2 4 2 1 2 1 4 4 4 4 4 1 1 1 2 4 1 1 1 1 19 1 1 1 4 1 2 4 2 1 1 1 4 2 1 2 2 4 1 1 1 2 1 1 1 2 2 4 1 4 1 1 4 4 4 1 1 1 2 4 38 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 19 4 2 2 1 1 4 1 5 4 7 5 1 1 11 2 1 1 1 9 3 1 1 1 9 2 2 1 1 1 2 18 3 2 1 9 1 3 2 3 1 1 1 3 1 9 1 3 2 ...
output:
? 23 32 ? 43 15 ? 43 1 ? 43 2 ? 43 3 ? 43 4 ? 43 5 ? 43 6 ? 43 7 ? 43 8 ? 43 9 ? 43 10 ? 43 11 ? 43 12 ? 43 13 ? 43 14 ? 43 15 ? 43 16 ? 43 17 ? 43 18 ? 43 19 ? 43 20 ? 43 21 ? 43 22 ? 43 23 ? 43 24 ? 43 25 ? 43 26 ? 43 27 ? 43 28 ? 43 29 ? 43 30 ? 43 31 ? 43 32 ? 43 33 ? 43 34 ? 43 35 ? 43 36 ? 43 ...
result:
ok Primes are found successfully with S = 578453 queries total