QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116907 | #6668. Trokuti | xtqqwq# | 0 | 0ms | 0kb | C++14 | 3.5kb | 2023-06-30 10:20:07 | 2024-05-31 18:34:22 |
Judging History
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