QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116834#6668. Trokuticsy2005#0 0ms0kbC++143.6kb2023-06-30 09:04:542024-05-31 18:30:37

Judging History

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

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

answer

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#include<random>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
//typedef __int128 i128;
//typedef unsigned __int128 u128;
/*#ifndef ONLINE_JUDGE
	FILE *___=freopen(".in","r",stdin);
#endif*/
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=1065977431;
int qp(int x,int y){int z=1;while(y){if(y&1){z=1ll*z*x%mod;}x=1ll*x*x%mod;y/=2;}return z;}
mt19937 rnd(1064);
int n,m,i,j,k,p[105],g[105][105],res[105][105];
int a[15][15],_[105][105],cc;
int fa[205];int fnd(int x){if(fa[x]==x)return x;return fa[x]=fnd(fa[x]);}
int query(int x,int y,int z)
{
	x=p[x];y=p[y];z=p[z];
	printf("? %d %d %d\n",x,y,z);fflush(stdout);cc++;
//	return _[x][y]+_[x][z]+_[y][z];
	int s;scanf("%d",&s);return s;
}
int id(int x,int y)
{
	if(x==1) return y-1;
	if(x==2) return y+2;
	if(x==3) return y+4;
	if(x==4) return y+5;
	for(;;);
}
int main()
{
	n=100;fz1(i,n)p[i]=i;fz1(i,n)swap(p[i],p[rnd()%i+1]);
	fz1(i,n)fz(j,i+1,n)_[i][j]=_[j][i]=((i+j)&1);
	fz1(i,5)fz(j,i+1,5)fz(k,j+1,5){
		m++;a[m][id(i,j)]=a[m][id(i,k)]=a[m][id(j,k)]=1;
		a[m][11]=query(i,j,k);
	}
	fz1(i,10){
		int t=0;fz(j,i,10)if(a[j][i]){t=j;break;}
		assert(t);fz1(j,11)swap(a[t][j],a[i][j]);
		t=qp(a[i][i],mod-2);fz1(j,11)a[i][j]=1ll*a[i][j]*t%mod;
		fz1(j,10)if(j!=i){
			int t=(mod-a[j][i])%mod;
			fz1(k,11) a[j][k]=(a[j][k]+1ll*a[i][k]*t)%mod;
		}
	}
	fz1(i,5)fz(j,i+1,5) g[i][j]=g[j][i]=a[id(i,j)][11];
	fz(i,6,n){
		vector<int> v;
		fz1(j,n*2) fa[j]=j;
		fz1(j,i-1) v.push_back(j);
		fz0k(j,v.size())swap(v[j],v[rnd()%(j+1)]);
		while(v.size()>1){
			int x=v.back();v.pop_back();
			int y=v.back();v.pop_back();
			int t=query(x,y,i)-g[x][y];
			if(t==0){g[i][x]=g[i][y]=g[x][i]=g[y][i]=0;continue;}
			if(t==2){g[i][x]=g[i][y]=g[x][i]=g[y][i]=1;continue;}
			fa[fnd(x)]=fnd(y+n);fa[fnd(x+n)]=fnd(y);
			v.push_back(y);
		}
		if(v.size()==1){
			int x=v.back();
			fz1(j,i-1)if(j!=x&&fnd(j)==j){
				g[i][x]=g[x][i]=query(i,j,x)-g[i][j]-g[j][x];
				break;
			}
			for(;;);
		}
		fz1(j,i-1)if(fnd(j)!=j){
			if(fnd(j)<=n) g[i][j]=g[j][i]=g[i][fnd(j)];
			else g[i][j]=g[j][i]=(!g[i][fnd(j)-n]);
		}
	}
	fz1(i,n)fz1(j,n)if(g[i][j])res[p[i]][p[j]]=1;
	puts("!");fz1(i,n){fz1(j,n)printf("%d",res[i][j]);puts("");}fflush(stdout);
//	cerr<<cc<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

0
0
0
0
0
0
0
0
0
0
0
0
0

output:

? 21 9 93
? 21 9 27
? 21 9 5
? 21 93 27
? 21 93 5
? 21 27 5
? 9 93 27
? 9 93 5
? 9 27 5
? 93 27 5
? 9 93 50
? 21 27 50
? 50 21 5

result: