QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331630 | #8216. Jumbled Primes | ucup-team2303 | TL | 0ms | 0kb | C++14 | 4.2kb | 2024-02-18 16:06:16 | 2024-02-18 16:06:16 |
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);
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("! ");
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: 0
Time Limit Exceeded