QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126504 | #6668. Trokuti | honglan0301 | 0 | 9ms | 3656kb | C++14 | 3.9kb | 2023-07-18 15:36:26 | 2023-07-18 15:36:29 |
Judging History
answer
/*
author: PEKKA_l
Sexy_goodier _ xiaoqing
*/
#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <set>
#include <assert.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mod 998244353
int n=100,a[105][105],zt[105][105],p[105],in[105],na,cnt,x1,x2,x3,cntq,q[105];
vector <int> nd;
int ask(int u,int v,int w)
{
cnt++; assert(u!=v&&v!=w&&u!=w);
int na=a[u][v]+a[v][w]+a[u][w]; return na;
}
int solve(int u,int v,int w)
{
x1=(u-v+w)/2; x2=v-x1; x3=w-x1;
}
signed main()
{
srand(time(0)); //for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) a[i][j]=a[j][i]=rand()&1;
//for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
for(int i=1;i<=n;i++) p[i]=i; //random_shuffle(p+1,p+n+1);
for(int i=1;i<=6;i++)
{
for(int j=i+1;j<=6;j++)
{
for(int k=j+1;k<=6;k++)
{
if(nd.size()) continue;
cout<<"? "<<p[i]<<" "<<p[j]<<" "<<p[k]<<endl;
//na=ask(p[i],p[j],p[k]); //cout<<p[i]<<" "<<p[j]<<" "<<p[k]<<" "<<na<<endl;
cin>>na;
if(na==0)
{
//cout<<i<<" "<<j<<" "<<k<<endl;
nd.pb(p[i]); nd.pb(p[j]); nd.pb(p[k]);
in[p[i]]=in[p[j]]=in[p[k]]=1;
}
else if(na==3)
{
nd.pb(p[i]); nd.pb(p[j]); nd.pb(p[k]);
in[p[i]]=in[p[j]]=in[p[k]]=1;
zt[p[i]][p[j]]=zt[p[j]][p[i]]=zt[p[i]][p[k]]=zt[p[k]][p[i]]=zt[p[j]][p[k]]=zt[p[k]][p[j]]=1;
}
}
}
}
for(int i=1;i<=n;i++)
{
if(in[p[i]]) continue; cntq=0; for(auto j:nd) q[++cntq]=j;
//random_shuffle(q+1,q+cntq+1);
int nz=1;
// cout<<"G "<<i<<" "<<p[i]<<" "<<cntq<<endl; for(int j=1;j<=cntq;j++) cout<<q[j]<<" "; cout<<endl;
while(nz+2<=cntq)
{
cout<<"? "<<p[i]<<" "<<q[nz]<<" "<<q[nz+1]<<endl;
int nab=0; cin>>nab; nab-=zt[q[nz]][q[nz+1]];
//int nab=ask(p[i],q[nz],q[nz+1])-zt[q[nz]][q[nz+1]]; //cout<<p[i]<<" "<<q[nz]<<" "<<q[nz+1]<<" "<<nab<<endl;
if(nab==0||nab==2)
{
zt[p[i]][q[nz]]=zt[q[nz]][p[i]]=zt[p[i]][q[nz+1]]=zt[q[nz+1]][p[i]]=nab/2;
nz+=2; continue;
}
cout<<"? "<<p[i]<<" "<<q[nz+1]<<" "<<q[nz+2]<<endl;
int nbc=0; cin>>nbc; nbc-=zt[q[nz+1]][q[nz+2]];
//int nbc=ask(p[i],q[nz+1],q[nz+2])-zt[q[nz+1]][q[nz+2]]; //cout<<p[i]<<" "<<q[nz+1]<<" "<<q[nz+2]<<" "<<nbc<<endl;
if(nbc==0||nbc==2)
{
zt[p[i]][q[nz+1]]=zt[q[nz+1]][p[i]]=zt[p[i]][q[nz+2]]=zt[q[nz+2]][p[i]]=nbc/2;
zt[p[i]][q[nz]]=zt[q[nz]][p[i]]=nab-zt[p[i]][q[nz+1]];
nz+=3; continue;
}
cout<<"? "<<p[i]<<" "<<q[nz]<<" "<<q[nz+2]<<endl;
int nac=0; cin>>nac; nac-=zt[q[nz]][q[nz+2]];
//int nac=ask(p[i],q[nz],q[nz+2])-zt[q[nz]][q[nz+2]]; //cout<<p[i]<<" "<<q[nz]<<" "<<q[nz+2]<<" "<<nac<<endl;
solve(nab,nbc,nac); //cout<<"FF "<<x1<<" "<<x2<<" "<<x3<<endl;
zt[p[i]][q[nz]]=zt[q[nz]][p[i]]=x1;
zt[p[i]][q[nz+1]]=zt[q[nz+1]][p[i]]=x2;
zt[p[i]][q[nz+2]]=zt[q[nz+2]][p[i]]=x3;
nz+=3;
}
if(nz<=cntq)
{
cout<<"? "<<p[i]<<" "<<q[nz-1]<<" "<<q[nz]<<endl;
int nkk=0; cin>>nkk; nkk-=zt[p[i]][q[nz-1]]+zt[q[nz-1]][q[nz]];
//int nkk=ask(p[i],q[nz-1],q[nz])-zt[p[i]][q[nz-1]]-zt[q[nz-1]][q[nz]];
zt[p[i]][q[nz]]=zt[q[nz]][p[i]]=nkk;
}
if(nz+1<=cntq)
{
cout<<"? "<<p[i]<<" "<<q[nz-1]<<" "<<q[nz+1]<<endl;
int nkk=0; cin>>nkk; nkk-=zt[p[i]][q[nz-1]]+zt[q[nz-1]][q[nz+1]];
//int nkk=ask(p[i],q[nz-1],q[nz+1])-zt[p[i]][q[nz-1]]-zt[q[nz-1]][q[nz+1]];
zt[p[i]][q[nz+1]]=zt[q[nz+1]][p[i]]=nkk;
}
nd.pb(p[i]); in[p[i]]=1;
}
/*for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i][j]!=zt[i][j])
{
cout<<"WA "<<i<<" "<<j<<" "<<a[i][j]<<" "<<zt[i][j]<<endl;
}*/
cout<<"!"<<endl; //cout<<cnt<<endl;
for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) cout<<zt[i][j]; cout<<endl;}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 100
Accepted
time: 4ms
memory: 3636kb
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:
? 1 2 3 ? 4 1 2 ? 4 2 3 ? 5 1 2 ? 5 2 3 ? 5 2 4 ? 6 1 2 ? 6 3 4 ? 6 4 5 ? 7 1 2 ? 7 3 4 ? 7 4 5 ? 7 4 6 ? 8 1 2 ? 8 3 4 ? 8 5 6 ? 8 6 7 ? 9 1 2 ? 9 3 4 ? 9 5 6 ? 9 6 7 ? 9 6 8 ? 10 1 2 ? 10 3 4 ? 10 5 6 ? 10 7 8 ? 10 8 9 ? 11 1 2 ? 11 3 4 ? 11 5 6 ? 11 7 8 ? 11 8 9 ? 11 8 10 ? 12 1 2 ? 12 3 4 ? 12 5...
result:
points 1.0 points 1.0 correct 2547 queries
Test #2:
score: 100
Accepted
time: 4ms
memory: 3656kb
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:
? 1 2 3 ? 4 1 2 ? 4 2 3 ? 5 1 2 ? 5 2 3 ? 5 2 4 ? 6 1 2 ? 6 3 4 ? 6 4 5 ? 7 1 2 ? 7 3 4 ? 7 4 5 ? 7 4 6 ? 8 1 2 ? 8 3 4 ? 8 5 6 ? 8 6 7 ? 9 1 2 ? 9 3 4 ? 9 5 6 ? 9 6 7 ? 9 6 8 ? 10 1 2 ? 10 3 4 ? 10 5 6 ? 10 7 8 ? 10 8 9 ? 11 1 2 ? 11 3 4 ? 11 5 6 ? 11 7 8 ? 11 8 9 ? 11 8 10 ? 12 1 2 ? 12 3 4 ? 12 5...
result:
points 1.0 points 1.0 correct 2547 queries
Test #3:
score: 100
Accepted
time: 9ms
memory: 3556kb
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:
? 1 2 3 ? 4 1 2 ? 4 2 3 ? 5 1 2 ? 5 2 3 ? 5 2 4 ? 6 1 2 ? 6 3 4 ? 6 4 5 ? 7 1 2 ? 7 3 4 ? 7 4 5 ? 7 4 6 ? 8 1 2 ? 8 3 4 ? 8 5 6 ? 8 6 7 ? 9 1 2 ? 9 3 4 ? 9 5 6 ? 9 6 7 ? 9 6 8 ? 10 1 2 ? 10 3 4 ? 10 5 6 ? 10 7 8 ? 10 8 9 ? 11 1 2 ? 11 3 4 ? 11 5 6 ? 11 7 8 ? 11 8 9 ? 11 8 10 ? 12 1 2 ? 12 3 4 ? 12 5...
result:
points 1.0 points 1.0 correct 2548 queries
Test #4:
score: 0
Time Limit Exceeded
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:
? 1 2 3 ? 4 1 2 ? 4 2 3 ? 5 1 2 ? 5 2 3 ? 5 2 4 ? 6 1 2 ? 6 3 4 ? 6 4 5 ? 7 1 2 ? 7 3 4 ? 7 4 5 ? 7 4 6 ? 8 1 2 ? 8 3 4 ? 8 5 6 ? 8 6 7 ? 9 1 2 ? 9 3 4 ? 9 5 6 ? 9 6 7 ? 9 6 8 ? 10 1 2 ? 10 3 4 ? 10 5 6 ? 10 7 8 ? 10 8 9 ? 11 1 2 ? 11 3 4 ? 11 5 6 ? 11 7 8 ? 11 8 9 ? 11 8 10 ? 12 1 2 ? 12 3 4 ? 12 5...