QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117019#6668. Trokutiyoungsystem#0 8ms3844kbC++204.4kb2023-06-30 12:15:432024-05-31 18:37:35

Judging History

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

  • [2024-05-31 18:37:35]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:3844kb
  • [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:15:43]
  • 提交

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);
	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=7;
	for(int i=1;i<=100;i++)p[i]=i;
	for(int i=1;i<=100;i++)swap(p[ran()%i+1],p[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]];
			assert(sc[p[i]][p[j]]==yl[p[i]][p[j]]); 
		}
	}
	n=100;
	for(int i=8;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;
					}
				}
				int sth=ask(p[i],p[wz[1]],p[wz[2]])-sc[p[wz[1]]][p[wz[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;
			assert(sc[p[i]][p[j]]==yl[p[i]][p[j]]);
		}
	}
	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;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

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

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:

? 99 58 13
? 99 58 47
? 99 58 23
? 99 58 86
? 99 58 34
? 99 13 47
? 99 13 23
? 99 13 86
? 99 13 34
? 99 47 23
? 99 47 86
? 99 47 34
? 99 23 86
? 99 23 34
? 99 86 34
? 26 86 47
? 26 34 23
? 26 58 13
? 26 99 34
? 57 13 99
? 57 26 86
? 57 47 23
? 57 58 34
? 98 26 47
? 98 99 86
? 98 58 23
? 98 57 13
? 9...

result:

points 1.0 points  1.0 correct 2503 queries

Test #2:

score: 0
Runtime Error

input:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

output:

? 99 58 13
? 99 58 47
? 99 58 23
? 99 58 86
? 99 58 34
? 99 13 47
? 99 13 23
? 99 13 86
? 99 13 34
? 99 47 23
? 99 47 86
? 99 47 34
? 99 23 86
? 99 23 34
? 99 86 34

result: