QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116827 | #6668. Trokuti | csy2005# | 0 | 9ms | 4172kb | C++14 | 3.6kb | 2023-06-30 09:00:13 | 2024-05-31 18:30:30 |
Judging History
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)
{
printf("? %d %d %d\n",p[x],p[y],p[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;
assert(1064==822);
}
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;
}
assert(j<i);
}
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",g[i][j]);puts("");}fflush(stdout);
// cerr<<cc<<endl;
return 0;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 100
Accepted
time: 3ms
memory: 4092kb
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 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2504 queries
Test #2:
score: 100
Accepted
time: 0ms
memory: 3876kb
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 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2504 queries
Test #3:
score: 100
Accepted
time: 0ms
memory: 3804kb
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 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2505 queries
Test #4:
score: 100
Accepted
time: 0ms
memory: 3888kb
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 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2505 queries
Test #5:
score: 100
Accepted
time: 8ms
memory: 3888kb
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 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 0 0 0 0 ...
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2511 queries
Test #6:
score: 100
Accepted
time: 0ms
memory: 3972kb
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 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 2512 queries
Test #7:
score: 100
Accepted
time: 5ms
memory: 4172kb
input:
0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 3 1 0 0 2 3 0 1 1 1 1 2 1 1 2 0 0 1 1 0 0 1 1 1 0 1 1 3 2 1 3 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 2 1 1 2 1 1 0 1 1 1 0 1 1 1 1 0 2 1 1 1 2 1 0 0 0 1 2 0 0 0 2 2 0 0 1 0 1 2 1 0 0 1 0 3 0 2 1 2 1 1 1 1 1 1 0 0 0 0 2 3 1 0 1 1 1 2 0 1 2 0 1 1 0 1 0 0 1 2 1 0 0 0 0 3 1 2 0 ...
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 4 2 6 ? 3 2 7 ? 6 1 7 ? 1 5 7 ? 7 1 4 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 4 6 9 ? 6 7 9 ? 7 2 9 ? 2 8 9 ? 9 1 8 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 7 9 11 ? 6 5 11 ? 10...
result:
points 1.0 points 1.0 correct 3111 queries
Test #8:
score: 100
Accepted
time: 0ms
memory: 3888kb
input:
3 1 2 1 2 1 1 1 0 0 1 0 1 2 1 1 1 1 2 2 0 1 1 1 2 3 1 1 0 0 2 1 0 3 2 1 1 1 2 2 1 1 2 2 0 1 1 0 0 0 0 1 2 2 2 1 2 2 2 1 1 1 1 0 2 2 0 0 0 0 2 1 2 1 0 2 1 3 0 1 2 0 2 1 1 1 0 1 1 2 2 2 1 0 2 2 1 0 2 1 1 1 0 3 1 1 1 0 3 2 0 1 2 0 3 0 1 2 0 2 1 1 0 1 1 1 1 1 0 1 2 1 2 1 0 1 3 2 2 1 1 2 1 1 1 2 0 3 1 1 ...
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 2 6 7 ? 6 1 7 ? 1 5 7 ? 7 1 4 ? 6 7 8 ? 7 3 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 9 1 8 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 7 3 10 ? 4 2 10 ? 4 7 11 ? 9 6 11 ? 6 5 11 ? 5 ...
result:
points 1.0 points 1.0 correct 3223 queries
Test #9:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
2 2 2 3 3 2 1 1 0 2 3 2 0 1 0 3 2 1 3 2 2 1 3 3 1 0 1 1 3 3 2 2 1 3 0 1 2 0 2 2 3 1 3 2 2 1 0 2 1 2 3 2 0 2 1 3 1 2 2 1 1 1 0 0 2 2 3 2 0 3 2 3 2 1 1 0 2 0 1 2 3 3 1 0 2 0 2 0 0 3 2 3 1 3 2 2 2 2 1 0 0 0 3 3 0 0 3 0 0 2 2 3 1 0 3 1 2 0 1 1 2 0 3 2 0 1 0 1 3 3 0 1 1 1 2 0 2 3 2 2 2 2 3 0 3 0 1 2 1 2 ...
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 4 2 6 ? 3 2 7 ? 2 6 7 ? 1 5 7 ? 7 1 4 ? 6 7 8 ? 7 3 8 ? 4 1 8 ? 1 2 8 ? 2 5 8 ? 8 3 5 ? 3 1 9 ? 5 4 9 ? 4 6 9 ? 7 2 9 ? 2 8 9 ? 9 1 8 ? 5 8 10 ? 9 1 10 ? 1 6 10 ? 6 7 10 ? 7 3 10 ? 4 2 10 ? 4 7 11 ? 7 9...
result:
points 1.0 points 1.0 correct 3340 queries
Test #10:
score: 100
Accepted
time: 9ms
memory: 3900kb
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 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 3 4 6 ? 6 1 2 ? 3 2 7 ? 6 1 7 ? 5 4 7 ? 6 7 8 ? 3 4 8 ? 1 2 8 ? 8 1 5 ? 3 1 9 ? 5 4 9 ? 6 7 9 ? 2 8 9 ? 5 8 10 ? 9 1 10 ? 6 7 10 ? 3 4 10 ? 10 1 2 ? 4 7 11 ? 9 6 11 ? 5 10 11 ? 1 3 11 ? 2 8 11 ? 5 11 12 ? 7 2 1...
result:
points 1.0 points 1.0 correct 3017 queries
Test #11:
score: 0
Runtime Error
input:
2 1 1 1 1 0 2 2 0 2 1 1 2 1
output:
? 1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5 ? 5 1 6 ? 1 3 6 ? 3 4 6 ? 4 2 6