QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116907#6668. Trokutixtqqwq#0 0ms0kbC++143.5kb2023-06-30 10:20:072024-05-31 18:34:22

Judging History

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

  • [2024-05-31 18:34:22]
  • 评测
  • 测评结果: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 10:20:07]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n=100,cur;
int ans[40],c[105][105],col[105],f[105];
vector<int> adj[105];
bool vis[105];
mt19937 mrand(1);

int ask(int x,int y,int z){
	printf("? %d %d %d\n",x,y,z);
	fflush(stdout);
	return readint();
}

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

void merge(int x,int y){
	int fx=getf(x),fy=getf(y);
	if(fx==fy) return;
	f[fx]=fy;
}

void dfs(int u){
	vis[u]=1;
	for(auto v:adj[u]){
		if(vis[v]) continue;
		c[cur][v]=c[v][cur]=c[cur][u]^1;
		dfs(v);
	}
}

void color(int u,int fa){
	for(auto v:adj[u]){
		if(v==fa) continue;
		col[v]=col[u]^1;
		color(v,u);
	}
}

void init(){
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=-1;
	for(int i=1;i<=n;i++) c[i][i]=0;
	for(int i=0;i<(1<<5);i++){
		vector<int> vec;
		for(int j=0;j<5;j++) if((i>>j)&1) vec.pb(j+1);
		if(vec.size()==3) ans[i]=ask(vec[0],vec[1],vec[2]);
	}
	for(int i=0;i<(1<<10);i++){
		int num=0;
		for(int j=1;j<=5;j++){
			for(int k=j+1;k<=5;k++){
				c[j][k]=c[k][j]=(i>>num)&1;
				num++;
			}
		}
		bool fl=0;
		for(int j=0;j<(1<<5);j++){
			vector<int> vec;
			for(int k=0;k<5;k++) if((j>>k)&1) vec.pb(k+1);
			if(vec.size()==3){
				if(c[vec[0]][vec[1]]+c[vec[0]][vec[2]]+c[vec[1]][vec[2]]!=ans[j]) fl=1;
			}
		}
		if(!fl) break;
	}
	for(int i=6;i<=n;i++){
		cur=i;
		vector<int> vec;
		for(int j=1;j<i;j++) vec.pb(j);
		for(int j=1;j<i;j++) adj[j].clear();
		for(int j=1;j<i;j++) vis[j]=0;
		while(vec.size()>1){
			int x=mrand()%vec.size(),y=mrand()%(vec.size()-1);
			if(x==y) y++;
			int tmp=ask(vec[x],vec[y],i)-c[vec[x]][vec[y]];
			if(tmp==0) c[i][vec[x]]=c[vec[x]][i]=c[i][vec[y]]=c[vec[y]][i]=0;
			else if(tmp==2) c[i][vec[x]]=c[vec[x]][i]=c[i][vec[y]]=c[vec[y]][i]=1;
			else adj[vec[x]].pb(vec[y]),adj[vec[y]].pb(vec[x]);
			vector<int> th;
			for(auto r:vec) if(r!=vec[x]&&r!=vec[y]) th.pb(r);
			swap(vec,th);
		}
		for(int j=1;j<i;j++) if(!vis[j]&&c[i][j]>=0) dfs(j);
		for(int j=1;j<i;j++) f[j]=j;
		for(int j=1;j<i;j++) for(auto v:adj[j]) merge(j,v);
		for(int j=1;j<i;j++){
			if(c[i][j]>=0) continue;
			for(int k=j+1;k<i;k++){
				if(c[i][k]>=0) continue;
				if(getf(j)==getf(k)) continue;
				int tmp=ask(j,k,i)-c[j][k];
				if(tmp==0){
					c[i][j]=c[j][i]=c[i][k]=c[k][i]=0;
					dfs(j);
					if(!vis[k]) dfs(k);
				}
				else if(tmp==2){
					c[i][j]=c[j][i]=c[i][k]=c[k][i]=1;
					dfs(j);
					if(!vis[k]) dfs(k);
				}
				else adj[j].pb(k),adj[k].pb(j),merge(j,k);
			}
		}
		for(int j=1;j<i;j++){
			if(c[i][j]>=0) continue;
			col[j]=0; color(j,-1);
		}
		pii cho;
		for(int j=1;j<i;j++) for(int k=j+1;k<i;k++) if(c[i][j]==-1&&c[i][k]==-1&&col[j]==col[k]) cho=mp(j,k);
		int tmp=ask(cho.fi,cho.se,i)-c[cho.fi][cho.se];
		if(tmp==0){
			c[i][cho.fi]=c[cho.fi][i]=c[i][cho.se]=c[cho.se][i]=0;
			dfs(cho.fi);
		}
		else{
			c[i][cho.fi]=c[cho.fi][i]=c[i][cho.se]=c[cho.se][i]=1;
			dfs(cho.fi);
		}
	}
}

int main(){
	init();
	return 0;
}

详细

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

output:

? 1 2 3
? 1 2 4
? 1 3 4
? 2 3 4
? 1 2 5
? 1 3 5
? 2 3 5
? 1 4 5
? 2 4 5
? 3 4 5
? 1 4 6
? 2 3 6
? 0 0 6

result: