QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117046#6668. Trokutiyoungsystem#0 11ms5912kbC++204.4kb2023-06-30 12:37:272024-05-31 18:38:55

Judging History

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

  • [2024-05-31 18:38:55]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:5912kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 12:37:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int ans[105][105][105];
int sc[105][105];
int yl[105][105];
int p[105];
mt19937 ran(121296);
int xl1[105],cnt1;
int xl2[105],cnt2;
int wz[105],tmp;
int fa[205],nqd[205];
int findf(int n)
{
	if(fa[n]==n)return n;
	return fa[n]=findf(fa[n]);
}
void merge(int x,int y)
{
	x=findf(x);
	y=findf(y);
	assert(nqd[x]==-1&&nqd[y]==-1);
	fa[x]=y;
}
int qsl;
int ask(int i,int j,int k)
{
	qsl++;
	assert(qsl<=100000);
	printf("? %d %d %d\n",i,j,k);
	fflush(stdout);
	int ans=read();
	return ans;
}
int main()
{
	/*for(int i=1;i<=100;i++)
	{
		for(int j=i+1;j<=100;j++)
		{
			yl[i][j]=ran()%2;
			yl[j][i]=yl[i][j];
		}
	}*/
	int n=10;
	for(int i=1;i<=100;i++)p[i]=i;
	for(int i=2;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			ans[p[1]][p[i]][p[j]]=ask(p[1],p[i],p[j]);
			ans[p[1]][p[j]][p[i]]=ans[p[1]][p[i]][p[j]]; 
		}
	}
	for(int i=2;i<=n;i++)
	{
		cnt1=cnt2=0;
		bool qd=false;
		for(int j=2;j<=n;j++)
		{
			if(j==i)continue;
			if(ans[p[1]][p[i]][p[j]]==0)
			{
				qd=true;
				sc[p[1]][p[i]]=0;
				break;
			}
			if(ans[p[1]][p[i]][p[j]]==3)
			{
				qd=true;
				sc[p[1]][p[i]]=1;
				break;
			}
			if(ans[p[1]][p[i]][p[j]]==1)xl1[++cnt1]=j;
			else xl2[++cnt2]=j;
		}
		if(qd)continue;
		if(cnt1>=3)
		{
			int sth=ask(p[xl1[1]],p[xl1[2]],p[xl1[3]]);
			if(sth!=0)
			{
				sc[p[1]][p[i]]=0;
				continue;
			}
			if(ans[p[1]][p[xl1[1]]][p[xl1[2]]]>=2)sc[p[1]][p[i]]=0;
			else sc[p[1]][p[i]]=1;
		}
		else
		{
			int sth=ask(p[xl2[1]],p[xl2[2]],p[xl2[3]]);
			if(sth!=3)
			{
				sc[p[1]][p[i]]=1;
				continue;
			}
			if(ans[p[1]][p[xl2[1]]][p[xl2[2]]]>=2)sc[p[1]][p[i]]=0;
			else sc[p[1]][p[i]]=1;
		}
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			sc[p[i]][p[j]]=ans[p[1]][p[i]][p[j]]-sc[p[1]][p[i]]-sc[p[1]][p[j]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			sc[p[j]][p[i]]=sc[p[i]][p[j]];
		}
	}
	n=100;
	for(int i=11;i<=n;i++)
	{
		for(int j=1;j<=2*(i-1);j++)
		{
			fa[j]=j;
			nqd[j]=-1;
		}
		int x,y;
		while(1)
		{
			tmp=0;
			for(int j=1;j<=(i-1);j++)
			{
				if(findf(j)==j&&nqd[j]==-1)wz[++tmp]=j;
			}
			//printf("!!!%d\n",tmp);
			if(tmp==0)break;
			if(tmp>=2)
			{
				int x=ran()%tmp+1,y=ran()%tmp+1;
				while(x==y)
				{
					x=ran()%tmp+1;
					y=ran()%tmp+1;
				}
				//printf("orz%d %d %d\n",x,y,tmp);
				int sth=ask(p[i],p[wz[x]],p[wz[y]])-sc[p[wz[x]]][p[wz[y]]];
				//printf("%d %d %d\n",wz[x],wz[y],sth);
				if(sth==0)
				{
					merge(wz[x],wz[y]);
					merge(wz[x]+i-1,wz[y]+i-1);
					nqd[findf(wz[x])]=0;
					nqd[findf(wz[x]+i-1)]=1;
				}
				else if(sth==2)
				{
					merge(wz[x],wz[y]);
					merge(wz[x]+i-1,wz[y]+i-1);
					nqd[findf(wz[x])]=1;
					nqd[findf(wz[x]+i-1)]=0;
				}
				else
				{
					merge(wz[x],wz[y]+i-1);
					merge(wz[x]+i-1,wz[y]);
				}
			}
			else
			{
				tmp=0;
				for(int j=1;j<=i-1;j++)
				{
					if(findf(j)<=i-1&&nqd[findf(j)]==-1)wz[++tmp]=j;
				}
				int gre=0;
				for(int j=1;j<=i-1;j++)
				{
					if(nqd[findf(j)]!=-1)gre=j;
				}
				if(gre!=0)
				{
					int sth=ask(p[i],p[wz[1]],p[gre])-sc[p[wz[1]]][p[gre]]-nqd[findf(gre)];
					if(sth==0)
					{
						nqd[findf(wz[1])]=0;
						nqd[findf(wz[1]+i-1)]=1;
					}
					else
					{
						nqd[findf(wz[1])]=1;
						nqd[findf(wz[1]+i-1)]=0;
					}
					break;
				}
				if(tmp<=1)
				{
					tmp=0;
					for(int j=1;j<=i-1;j++)
					{
						if(findf(j)>i-1&&nqd[findf(j)]==-1)wz[++tmp]=j;
					}
				}
				assert(tmp>=2);
				assert(findf(wz[1])==findf(wz[2]));
				int sth=ask(p[i],p[wz[1]],p[wz[2]])-sc[p[wz[1]]][p[wz[2]]];
				assert(sth==0||sth==2);
				if(sth==2)
				{
					nqd[findf(wz[1])]=1;
					nqd[findf(wz[1]+i-1)]=0;
				}
				else
				{
					nqd[findf(wz[1])]=0;
					nqd[findf(wz[1]+i-1)]=1;
				}
				break; 
			}
		}
		for(int j=1;j<=i-1;j++)
		{
			if(nqd[findf(j)]==1)sc[p[i]][p[j]]=sc[p[j]][p[i]]=1;
			else sc[p[i]][p[j]]=sc[p[j]][p[i]]=0;
		}
	}
	printf("!\n");
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%d",sc[i][j]);
		}
		printf("\n");
	}
	fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 100
Accepted
time: 11ms
memory: 3828kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2511 queries

Test #2:

score: 100
Accepted
time: 0ms
memory: 3908kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2511 queries

Test #3:

score: 100
Accepted
time: 0ms
memory: 3968kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2512 queries

Test #4:

score: 100
Accepted
time: 0ms
memory: 3896kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2512 queries

Test #5:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2521 queries

Test #6:

score: 100
Accepted
time: 8ms
memory: 5912kb

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
3
3
2
3
3
3
2
3
3
3
3
3
3
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 11...

result:

points 1.0 points  1.0 correct 2519 queries

Test #7:

score: 100
Accepted
time: 11ms
memory: 3884kb

input:

0
0
1
0
1
2
1
1
0
1
1
1
1
0
1
1
0
1
1
0
1
1
3
3
2
2
1
1
1
1
2
1
2
1
2
2
0
0
1
1
0
1
1
0
1
1
2
0
2
2
1
2
0
0
2
1
1
1
2
1
2
0
1
1
0
0
1
0
1
1
0
1
0
1
2
1
1
2
1
2
0
0
0
2
2
2
0
0
2
0
0
1
0
1
0
1
2
0
3
1
0
1
0
0
1
1
0
2
2
0
1
2
1
1
1
1
2
2
0
1
0
1
1
0
1
0
0
1
2
2
2
1
0
0
1
1
1
1
0
2
1
1
1
1
2
0
1
2
2
1
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 2 ...

result:

points 1.0 points  1.0 correct 3142 queries

Test #8:

score: 0
Wrong Answer
time: 5ms
memory: 3944kb

input:

3
1
2
1
1
1
1
1
1
2
1
2
1
1
1
1
0
1
0
1
0
1
1
1
2
1
1
0
1
1
1
1
0
1
0
0
2
2
1
2
2
2
2
1
0
1
1
2
0
0
1
1
1
2
1
0
1
3
1
0
1
1
1
1
1
1
1
1
1
2
0
0
1
2
0
2
2
2
2
2
1
1
1
0
0
3
2
0
1
2
1
2
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
1
1
1
1
2
2
2
0
1
1
3
3
1
2
1
2
0
1
0
0
2
2
2
1
1
2
0
0
1
1
1
1
0
2
1
1
1
2
0
1
0
1
1
...

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 2 6
? 1 2 7
? 1 2 8
? 1 2 9
? 1 2 10
? 1 3 4
? 1 3 5
? 1 3 6
? 1 3 7
? 1 3 8
? 1 3 9
? 1 3 10
? 1 4 5
? 1 4 6
? 1 4 7
? 1 4 8
? 1 4 9
? 1 4 10
? 1 5 6
? 1 5 7
? 1 5 8
? 1 5 9
? 1 5 10
? 1 6 7
? 1 6 8
? 1 6 9
? 1 6 10
? 1 7 8
? 1 7 9
? 1 7 10
? 1 8 9
? 1 8 10
? 1 9 10
? 4 ...

result:

wrong answer Token parameter [name=ans_i] equals to "011101112101001110100100001111...1101100001111111001010011011010", doesn't correspond to pattern "[01]{100,100}"