QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331630#8216. Jumbled Primesucup-team2303TL 0ms0kbC++144.2kb2024-02-18 16:06:162024-02-18 16:06:16

Judging History

你现在查看的是最新测评结果

  • [2024-02-18 16:06:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

input:


output:


result: