QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116978 | #6668. Trokuti | Irisu# | 0 | 0ms | 0kb | C++17 | 3.6kb | 2023-06-30 11:46:09 | 2024-05-31 18:36:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(19260817);
//mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(y<x)x=y;}
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))
typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;
const int n=100;
const bool Irisu=0;
bool mp[105][105];int sf[105],fs[105];int use_q=0;
bool ans[105][105];
struct Querys{
int a,b,c,v;
};
vector<Querys>Q;
int ask(int a,int b,int c){
int v;
a=sf[a],b=sf[b],c=sf[c];
if(Irisu){
use_q++;
v=mp[a][b]+mp[b][c]+mp[a][c];
Q.pb({fs[a],fs[b],fs[c],v});
return v;
}
printf("? %d %d %d\n",a,b,c);
fflush(stdout);
scanf("%d",&v);
Q.pb({fs[a],fs[b],fs[c],v});
return v;
}
void answer(){
if(Irisu){
bool asf=1;
rep(i,1,n)rep(j,1,n)asf&=ans[fs[i]][fs[j]]==mp[i][j];
if(asf){
puts("AC");
printf("count : %d\n",use_q);
}else{
puts("WA");
}
return;
}
puts("!");
rep(i,1,n){
rep(j,1,n)putchar(ans[fs[i]][fs[j]]|48);
puts("");
}
}
const int maxn=5000;
const int m=4950;
int tid[105][105];pii dit[maxn];
typedef bitset<maxn>bit;
int rk;
bit B[maxn];bool bb[maxn];
bool ins(bit&x){
per(i,m,1)if(x[i]){
if(bb[i]){
x^=B[i];continue;
}
rk++;
bb[i]=1;
B[i]=x;
return 1;
}
return 0;
}
void solve(){
if(Irisu){
rep(i,1,n)rep(j,i+1,n)mp[i][j]=mp[j][i]=Rnd()%100<50;
rep(i,1,n)sf[i]=i;
shuffle(sf+1,sf+n+1,Rnd);
rep(i,1,n)fs[sf[i]]=i;
}
{
int c=0;
rep(i,1,n)rep(j,i+1,n)tid[i][j]=tid[j][i]=++c,dit[c]={i,j};
}
static int buk[maxn];
memset(buk,-1,sizeof buk);
vi is[2];
rep(s,3,n){
vector<pii>orz;
rep(a,1,s-1)rep(b,a+1,s-1){
orz.pb({a,b});
}
shuffle(ALL(orz),Rnd);
bit w;
for(auto[a,b]:orz){
w.reset();
w.set(tid[a][b]),w.set(tid[a][s]),w.set(tid[b][s]);
if(!ins(w))continue;
int v=ask(a,b,s);
if(v==0||v==3){
buk[tid[a][b]]=buk[tid[a][s]]=buk[tid[b][s]]=v>0;
w.reset(),w.set(tid[a][b]),ins(w);
w.reset(),w.set(tid[a][s]),ins(w);
w.reset(),w.set(tid[b][s]),ins(w);
}else{
}
if(rk==s*(s-1)/2){
// printf("#%d\n",s);
break;
}
}
}
static bit a[maxn*4];
int tot=0;
for(auto[x,y,z,v]:Q){
if(v>0&&v<3){
tot++;
a[tot].set(tid[x][y]);
a[tot].set(tid[x][z]);
a[tot].set(tid[y][z]);
if(v&1)a[tot].set(m+1);
}
}
rep(i,1,m)if(buk[i]!=-1){
tot++;
a[tot].set(i);
if(buk[i])a[tot].set(m+1);
}
rep(i,1,m){
bool hav=0;
rep(j,1,tot)hav|=a[j][i];
if(!hav)cout<<i<<endl;
assert(hav);
}
rep(i,1,m){
if(!a[i][i]){
rep(j,i+1,tot)if(a[j][i]){
swap(a[i],a[j]);break;
}
}
rep(j,i+1,tot)if(a[j][i]){
a[j]^=a[i];
}
}
per(i,m,1){
assert(a[i][i]);
buk[i]=a[i][m+1];
rep(j,1,i-1)if(a[j][i])a[j]^=a[i];
}
// printf("!%d, %d\n",rk,use_q);
rep(i,1,n)rep(j,i+1,n)ans[i][j]=ans[j][i]=buk[tid[i][j]];
answer();
}
signed main(){
// int T;cin>>T;while(T--)solve();
solve();
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
output:
? 0 0 0