QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117625#6668. Trokutivme500 16ms3868kbC++172.1kb2023-07-01 20:49:402023-07-01 20:49:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-01 20:49:42]
  • 评测
  • 测评结果:0
  • 用时:16ms
  • 内存:3868kb
  • [2023-07-01 20:49:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 105
#define MOD 998244353
mt19937 rand1(0);
int n=100,nw,w[N],rt[N],st[N],a[N][N],z[N][N];
int f(int x,int y) {return (x-1)*(x-2)/2+y;}
int rdm(int l,int r) {return uniform_int_distribution<int>(l,r)(rand1);}
int qry(int x1,int x2,int x3)
{printf("? %d %d %d\n",x1,x2,x3);fflush(stdout);int t;scanf("%d",&t);return t;}
int findRt(int u)
{if(u==rt[u]) return u;int t=findRt(rt[u]);w[u]^=w[rt[u]];return rt[u]=t;}
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int qPow(int x,int y)
{int res=1;for(;y;y/=2,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;return res;}
void Gauss(int n)
{
	for(int i=1,t,t1;i<=n;++i)
	{
		if(!a[i][i]) for(int j=i+1;j<=n;++j) if(a[j][i])
		{for(int k=i;k<=n+1;++k) swap(a[i][k],a[j][k]);break;}
		assert(a[i][i]);t=qPow(MOD-a[i][i],MOD-2);
		for(int j=i+1;j<=n;++j)
		{
			t1=1ll*t*a[j][i]%MOD;
			for(int k=i;k<=n+1;++k) a[j][k]=(a[j][k]+1ll*t1*a[i][k])%MOD;
		}
	}
	for(int i=n;i;--i)
	{
		for(int j=i+1;j<=n;++j) W(a[i][n+1],MOD-1ll*a[i][j]*a[j][n+1]%MOD);
		a[i][n+1]=1ll*a[i][n+1]*qPow(a[i][i],MOD-2)%MOD;
	}
}
int main()
{
	for(int i=1;i<=5;++i) for(int j=1;j<i;++j) for(int k=1;k<j;++k)
		++nw,a[nw][f(i,j)]=a[nw][f(j,k)]=a[nw][f(i,k)]=1,a[nw][11]=qry(i,j,k);
	Gauss(10);for(int i=1;i<=5;++i) for(int j=1;j<i;++j) z[i][j]=a[f(i,j)][11];
	for(int i=6,t,t1,t2;i<=n;++i)
	{
		iota(rt+1,rt+i,1);fill(w+1,w+i,0);fill(z[i]+1,z[i]+i,-1);
		while(1)
		{
			st[0]=0;for(int j=1;j<i;++j) if(findRt(j)==j && z[i][j]==-1) st[++st[0]]=j;
			if(!st[0]) break;
			if(st[0]==1)
			{
				if(st[1]>1) z[i][st[1]]=qry(i,1,st[1])-z[st[1]][1]-z[i][1];
				else z[i][1]=qry(i,1,2)-z[2][1]-z[i][2];break;
			}t1=t2=st[rdm(1,st[0])];while(t1==t2) t2=st[rdm(1,st[0])];
			t=qry(i,t1,t2)-z[max(t1,t2)][min(t1,t2)];
			if(t==1) rt[t1]=t2,w[t1]=1;else z[i][t1]=z[i][t2]=t/2;
		}for(int j=1;j<i;++j) if(z[i][j]==-1) t=findRt(j),z[i][j]=z[i][t]^w[j];
	}for(int i=1;i<=n;++i) for(int j=1;j<i;++j) z[j][i]=z[i][j];printf("!\n");
	for(int i=1;i<=n;++i,putchar('\n')) for(int j=1;j<=n;++j) putchar(z[i][j]+48);
	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: 16ms
memory: 3672kb

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:

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

result:

points 1.0 points  1.0 correct 2504 queries

Test #2:

score: 100
Accepted
time: 1ms
memory: 3868kb

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:

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

result:

points 1.0 points  1.0 correct 2504 queries

Test #3:

score: 100
Accepted
time: 2ms
memory: 3688kb

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:

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

result:

points 1.0 points  1.0 correct 2504 queries

Test #4:

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

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:

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

result:

points 1.0 points  1.0 correct 2504 queries

Test #5:

score: 100
Accepted
time: 1ms
memory: 3624kb

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
1
0
0
0
0
0
0
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:

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

result:

points 1.0 points  1.0 correct 2511 queries

Test #6:

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

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
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

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

result:

points 1.0 points  1.0 correct 2511 queries

Test #7:

score: 0
Wrong Answer
time: 9ms
memory: 3620kb

input:

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

output:

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

result:

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