QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117102#6668. TrokutiIrisu#34.470968 764ms12412kbC++175.6kb2023-06-30 12:55:112024-05-31 18:42:13

Judging History

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

  • [2024-05-31 18:42:13]
  • 评测
  • 测评结果:34.470968
  • 用时:764ms
  • 内存:12412kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 12:55:11]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")

#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;

#ifdef Arraiter
const bool Irisu=1;
#else
const bool Irisu=0;
#endif
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];

struct bit{
  u64 seq[78];
  void reset(){
    mem(seq);
  }
  void set(int pos){
    seq[pos>>6]|=1ull<<(pos&63);
  }
  void flip(int pos){
    seq[pos>>6]^=1ull<<(pos&63);
  }
  bool operator[](int pos)const{
    return seq[pos>>6]>>(pos&63)&1;
  }
  void operator^=(const bit&o){
    rep(i,0,77)seq[i]^=o.seq[i];
  }
  void doit_pre(const bit&o,int pos){
    rep(i,0,pos>>6)seq[i]^=o.seq[i];
  }
  void doit_suf(const bit&o,int pos){
    rep(i,pos>>6,77)seq[i]^=o.seq[i];
  }
};

//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];
      x.doit_pre(B[i],i);
      continue;
    }
    rk++;
    bb[i]=1;
    B[i]=x;
    return 1;
  }
  return 0;
}

void solve(){
  rep(i,1,n)sf[i]=i;
//  shuffle(sf+1,sf+n+1,Rnd);
  rep(i,1,n)fs[sf[i]]=i;
  if(Irisu){
//    rep(i,1,n)rep(j,i+1,n)mp[i][j]=mp[j][i]=i==1;
    rep(i,1,n)rep(j,i+1,n)mp[i][j]=mp[j][i]=Rnd()%100<50;
  }
  
  {
    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);
  
  bit w;
  auto upd=[&](int i,int v){
    if(buk[i]==-1){
      buk[i]=v;
      w.reset(),w.set(i),ins(w);
    }
  };
  rep(s,3,n){
    for(auto[x,y,z,v]:Q){
      int i=tid[x][y],j=tid[x][z],k=tid[y][z];
      if(v>0&&v<3){
        if(v==1){
          if(buk[i]==1||buk[j]==1||buk[k]==1){
            upd(i,0);
            upd(j,0);
            upd(k,0);
          }
        }
        if(v==2){
          if(buk[i]==0||buk[j]==0||buk[k]==0){
            upd(i,1);
            upd(j,1);
            upd(k,1);
          }
        }
      }
    }
    vector<pii>lef,rig;
    vi vis(m+1,0);
    rep(dt,1,s-1)
    rep(a,1,s-1-dt)if(!vis[tid[a][a+dt]])(buk[tid[a][a+dt]]!=-1?lef:rig).pb({a,a+dt}),vis[tid[a][a+dt]]=1;
//    vector<pii>lef,rig;
    rep(a,1,s-1)rep(b,a+1,s-1)if(!vis[tid[a][b]]){
      if(buk[tid[a][b]]!=-1&&0)rig.pb({a,b});
      else lef.pb({a,b});
    }
//    shuffle(ALL(lef),Rnd);
//    shuffle(ALL(rig),Rnd);
    for(auto p:rig)lef.pb(p);
    for(auto[a,b]:lef){
      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){
        upd(tid[a][b],v>0);
        upd(tid[a][s],v>0);
        upd(tid[s][b],v>0);
      }else{
        
      }
      if(rk==s*(s-1)/2){
//        printf("#%d\n",s);
        break;
      }
    }
  }
  
  static bit a[20000];
  int tot=0;
  for(auto[x,y,z,v]:Q){
    int i=tid[x][y],j=tid[x][z],k=tid[y][z];
    if(v>0&&v<3){
      if(v==1){
        if(buk[i]==1||buk[j]==1||buk[k]==1){
          if(buk[i]==-1)buk[i]=0;
          if(buk[j]==-1)buk[j]=0;
          if(buk[k]==-1)buk[k]=0;
        }
      }
      if(v==2){
        if(buk[i]==0||buk[j]==0||buk[k]==0){
          if(buk[i]==-1)buk[i]=1;
          if(buk[j]==-1)buk[j]=1;
          if(buk[k]==-1)buk[k]=1;
        }
      }
      if(buk[i]!=-1&&buk[j]!=-1&&buk[k]!=-1)continue;
      tot++;
      a[tot].set(i);
      a[tot].set(j);
      a[tot].set(k);
      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].doit_suf(a[i],i);
//      a[j]^=a[i];
    }
  }
  per(i,m,1){
    assert(a[i][i]);
    buk[i]=a[i][m+1];
    if(a[i][m+1]){
      rep(j,1,i-1)if(a[j][i]){
        a[j].flip(m+1);
      }
    }
  }
  
//  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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 34.471
Acceptable Answer

Test #1:

score: 34.471
Acceptable Answer
time: 59ms
memory: 11460kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #2:

score: 34.471
Acceptable Answer
time: 65ms
memory: 11612kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #3:

score: 34.471
Acceptable Answer
time: 49ms
memory: 11972kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #4:

score: 34.471
Acceptable Answer
time: 50ms
memory: 11604kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #5:

score: 34.471
Acceptable Answer
time: 38ms
memory: 11176kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #6:

score: 34.471
Acceptable Answer
time: 75ms
memory: 11012kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #7:

score: 61.1161
Acceptable Answer
time: 74ms
memory: 11644kb

input:

0
0
0
1
0
0
0
1
1
0
1
0
0
1
1
2
1
0
1
1
0
1
1
0
1
2
0
1
0
0
0
0
0
1
0
1
2
1
0
0
0
0
0
1
2
1
1
2
2
1
2
2
1
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
1
0
1
1
1
1
1
1
1
0
0
0
2
1
2
1
1
0
0
0
0
1
1
1
1
1
2
0
0
0
1
1
0
1
1
0
0
1
0
0
1
1
0
1
1
0
0
2
1
1
1
2
1
0
1
0
1
0
1
1
0
1
1
2
1
0
1
1
1
1
1
1
2
0
1
1
0
1
0
0
0
0
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 4 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 7 8 10
? 8 9 10
? 1 2 11
? 2 3 11
? 3...

result:

points 0.61116129030 points  0.61116129030 correct 4261 queries

Test #8:

score: 59.4903
Acceptable Answer
time: 81ms
memory: 11996kb

input:

3
1
1
2
1
0
1
1
0
0
1
2
2
1
1
1
1
0
0
0
1
1
1
1
2
2
2
2
1
1
0
0
1
1
0
1
3
2
1
2
1
2
1
2
0
1
1
0
0
0
1
1
2
0
0
2
1
0
1
2
2
0
0
1
2
2
2
1
1
1
1
1
1
1
0
0
2
1
0
0
1
1
0
0
1
0
0
1
3
2
1
1
0
1
0
0
2
2
2
1
1
1
1
0
0
0
1
0
1
3
1
0
0
1
0
2
2
1
1
1
1
0
0
2
1
1
2
1
2
0
2
2
1
1
1
1
2
2
2
2
1
1
1
1
2
1
1
1
1
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 5 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 5 7 9
? 6 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 8 9 10
? 5 7 10
? 6 8 10
? 1 ...

result:

points 0.59490322580 points  0.59490322580 correct 4297 queries

Test #9:

score: 66.2645
Acceptable Answer
time: 97ms
memory: 11804kb

input:

2
2
1
2
1
2
2
1
2
1
2
1
2
1
2
2
1
2
1
2
1
2
1
2
1
2
1
3
1
3
2
2
1
2
1
2
2
1
3
2
2
2
1
2
1
1
2
1
3
2
2
2
2
1
2
2
1
2
1
3
2
2
2
3
2
1
1
2
1
2
1
3
2
2
2
2
3
2
2
1
2
1
2
1
3
2
2
2
3
2
2
1
2
1
2
1
3
2
2
2
2
3
2
2
1
2
1
2
1
3
2
2
2
2
3
2
2
2
1
2
1
2
1
3
2
2
2
2
3
2
2
3
2
1
2
1
2
1
3
2
2
2
3
2
3
2
2
2
1
2
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 6 7 10
? 7 8 10
? 8 9 10
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 5 ...

result:

points 0.66264516130 points  0.66264516130 correct 4147 queries

Test #10:

score: 34.471
Acceptable Answer
time: 764ms
memory: 10216kb

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
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 ...

result:

points 0.34470967740 points  0.34470967740 correct 4851 queries

Test #11:

score: 51.7226
Acceptable Answer
time: 82ms
memory: 10784kb

input:

2
1
2
1
2
2
2
1
2
1
1
2
3
2
1
1
1
3
2
1
1
3
3
2
1
1
0
1
1
2
2
1
1
0
0
1
3
2
1
1
2
2
1
1
0
1
1
1
0
1
1
0
2
1
1
2
2
1
0
1
1
1
1
2
1
2
2
3
3
1
1
2
2
1
1
2
2
3
2
2
3
1
1
2
2
1
3
2
1
1
3
2
2
2
1
0
1
1
2
2
1
0
0
1
2
3
2
1
1
2
1
2
1
2
2
2
2
1
1
2
3
2
2
2
2
1
2
2
2
2
1
2
1
2
2
3
2
1
1
1
2
2
2
2
3
1
1
2
1
2
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 3 4 8
? 4 7 8
? 1 2 8
? 2 3 8
? 4 5 8
? 5 6 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 8 10
? 7 9 10
? 1 ...

result:

points 0.51722580650 points  0.51722580650 correct 4469 queries

Test #12:

score: 57.2323
Acceptable Answer
time: 71ms
memory: 12412kb

input:

1
1
3
1
2
2
0
2
2
1
1
2
1
2
0
1
1
2
1
3
1
1
1
2
1
3
2
1
0
2
2
0
2
2
1
2
1
3
3
2
2
3
3
2
1
3
2
0
1
2
2
0
2
2
1
2
2
2
2
2
2
1
2
2
2
0
2
2
0
2
2
2
1
2
1
1
1
2
2
1
1
2
1
2
1
1
2
3
0
0
2
2
0
3
3
3
2
2
3
1
2
1
1
1
1
2
2
1
1
1
2
1
1
1
2
2
2
2
2
2
1
2
3
2
2
3
1
1
2
2
2
1
2
2
1
2
2
2
1
0
2
3
1
3
2
0
2
1
1
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 3 6 7
? 4 5 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 6 7 8
? 5 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 6 7 9
? 7 8 9
? 5 7 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 6 7 10
? 7 8 10
? 5 7 10
? 7 9 10
? 1 ...

result:

points 0.57232258060 points  0.57232258060 correct 4347 queries

Test #13:

score: 59.8516
Acceptable Answer
time: 73ms
memory: 12204kb

input:

0
1
0
1
1
2
1
2
2
2
1
1
0
2
2
2
2
2
3
1
2
2
2
2
2
1
0
2
0
1
1
2
2
0
1
0
1
2
2
2
0
1
1
1
0
1
3
2
2
1
2
2
1
0
1
2
3
1
0
1
1
0
2
1
0
1
3
1
0
0
1
1
1
2
1
1
0
2
2
1
0
1
1
1
0
1
0
1
1
2
3
2
2
1
3
2
1
2
1
1
1
2
2
0
0
1
2
0
2
3
0
1
2
2
1
2
1
1
1
0
2
2
1
1
2
2
1
1
2
2
2
2
3
2
1
0
1
0
2
0
3
1
1
0
1
2
2
2
1
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 4 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 6 7 8
? 4 6 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 6 7 9
? 7 8 9
? 4 6 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 6 7 10
? 7 8 10
? 8 9 10
? 1 2 11
? 2 ...

result:

points 0.5985161290 points  0.5985161290 correct 4289 queries

Test #14:

score: 54.6129
Acceptable Answer
time: 70ms
memory: 10552kb

input:

2
2
1
3
2
1
3
3
2
1
3
3
2
1
2
2
1
2
1
2
1
2
2
0
1
1
1
2
2
2
1
1
2
1
2
3
3
2
1
1
1
1
1
1
1
2
2
1
2
1
3
1
3
2
0
0
1
2
1
0
1
3
2
2
2
1
2
1
2
3
2
1
2
1
2
1
3
2
2
2
2
1
0
0
2
2
2
1
2
3
2
2
2
3
3
2
2
3
1
2
1
2
2
2
0
0
0
2
2
0
1
3
1
2
1
2
2
3
3
1
0
0
1
2
1
1
3
1
2
1
2
2
2
1
2
2
2
1
1
2
1
0
2
2
2
1
1
2
2
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 5 6
? 2 3 6
? 3 4 6
? 1 2 7
? 5 6 7
? 2 3 7
? 3 4 7
? 1 2 8
? 5 6 8
? 6 7 8
? 2 5 8
? 2 3 8
? 3 4 8
? 1 2 9
? 5 6 9
? 6 7 9
? 7 8 9
? 2 5 9
? 2 3 9
? 3 4 9
? 1 2 10
? 5 6 10
? 6 7 10
? 7 8 10
? 8 9 10
? 2 5 10
? 2 3 10
? 3 4 10
? 1 2 11
? 5...

result:

points 0.54612903230 points  0.54612903230 correct 4405 queries

Test #15:

score: 55.0194
Acceptable Answer
time: 91ms
memory: 11584kb

input:

3
2
2
2
2
2
2
2
3
1
1
1
1
1
2
1
2
2
0
1
2
1
1
1
0
1
3
1
1
1
2
1
0
1
2
1
1
1
2
1
0
1
2
2
1
3
2
1
1
2
2
3
2
1
2
3
2
0
0
2
3
2
2
0
2
1
1
0
0
2
2
2
1
3
0
3
1
1
1
1
1
2
2
3
2
2
2
2
2
1
1
1
0
1
2
2
1
2
2
2
2
2
1
2
2
1
0
0
1
1
2
2
3
1
2
2
1
3
2
1
0
0
2
2
2
2
2
1
3
2
2
2
0
2
1
2
2
1
1
2
2
2
3
2
1
1
1
2
1
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 5 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 7 9 10
? 5 8 10
? 1 ...

result:

points 0.55019354840 points  0.55019354840 correct 4396 queries

Test #16:

score: 54.2516
Acceptable Answer
time: 79ms
memory: 12172kb

input:

2
2
2
2
0
1
1
1
3
1
1
0
2
2
2
1
1
2
0
1
2
3
2
2
0
1
2
1
2
2
3
2
2
2
1
1
2
1
3
1
1
3
2
2
1
2
0
2
1
0
1
2
2
2
1
2
2
3
2
1
1
2
2
2
2
2
2
1
1
1
2
3
0
2
0
1
1
2
1
3
2
2
3
2
2
1
1
2
1
1
2
2
2
1
2
2
1
1
1
1
2
2
2
2
2
1
2
0
0
1
0
2
1
2
1
1
1
3
1
1
3
2
1
2
1
2
1
3
2
0
1
1
2
2
3
2
2
3
1
2
2
2
1
1
1
1
2
1
2
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 5 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 5 8 10
? 5 9 10
? 1 ...

result:

points 0.5425161290 points  0.5425161290 correct 4413 queries

Test #17:

score: 57.0065
Acceptable Answer
time: 55ms
memory: 11476kb

input:

0
1
1
1
2
3
1
0
2
2
0
0
1
2
2
1
2
2
2
2
2
1
2
2
2
2
1
2
0
1
2
2
1
1
0
3
2
2
3
2
2
1
3
2
1
1
2
2
2
1
1
1
1
1
2
0
0
1
2
2
2
2
2
2
2
2
2
2
2
1
3
0
0
2
2
1
2
2
1
2
3
1
1
1
3
3
2
1
2
0
1
2
1
1
1
1
3
3
3
1
2
2
2
2
2
2
2
0
1
1
2
2
1
1
2
1
2
1
2
2
2
3
2
1
2
2
3
2
1
2
3
2
2
2
3
2
2
1
1
2
1
2
3
1
2
3
2
2
2
2
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 4 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 6 7 8
? 4 6 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 6 7 9
? 4 6 9
? 3 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 6 7 10
? 4 6 10
? 6 9 10
? 3 8 10
? 1 ...

result:

points 0.57006451610 points  0.57006451610 correct 4352 queries

Test #18:

score: 57.7742
Acceptable Answer
time: 64ms
memory: 11512kb

input:

1
2
2
1
2
2
0
1
1
3
2
1
2
2
2
0
1
1
3
2
2
1
1
1
3
2
3
1
1
1
3
2
2
2
3
1
3
1
1
1
2
3
2
2
3
1
2
2
2
3
2
2
0
2
1
2
2
1
1
1
1
2
1
1
1
0
2
3
1
2
1
2
2
0
1
3
2
3
3
1
2
1
1
1
2
0
1
2
1
1
2
2
1
1
1
2
1
0
1
1
2
2
1
2
2
2
2
2
2
2
2
1
2
1
2
1
3
2
3
2
3
3
2
1
2
3
3
2
1
2
1
1
0
1
1
2
1
1
1
2
2
1
1
0
1
3
0
2
1
2
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 3 4 7
? 4 5 7
? 5 6 7
? 2 4 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 2 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 7 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 7 8 10
? 8 9 10
? 5 8 10
? 1 2 11
? 2...

result:

points 0.57774193550 points  0.57774193550 correct 4335 queries

Test #19:

score: 54.8387
Acceptable Answer
time: 72ms
memory: 12292kb

input:

1
2
1
1
0
1
2
1
3
3
1
1
2
0
0
1
1
3
1
0
1
2
1
2
1
1
1
1
3
2
2
0
1
1
1
1
1
0
2
2
2
1
1
2
2
3
2
2
0
0
0
2
1
0
2
1
1
3
1
0
0
3
2
2
0
2
0
2
2
2
1
2
1
1
0
1
2
1
2
1
0
1
2
1
3
1
1
1
3
1
2
1
1
1
3
2
3
1
0
0
0
2
1
3
1
1
2
1
1
2
0
0
0
0
2
2
2
0
0
1
3
2
2
1
1
0
0
2
3
2
2
1
1
1
3
2
3
2
2
2
1
0
1
2
1
2
2
2
1
1
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 2 3 6
? 3 5 6
? 1 2 6
? 3 4 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 6 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 7 9
? 6 8 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 6 7 10
? 6 8 10
? 8 9 10
? 1 ...

result:

points 0.54838709680 points  0.54838709680 correct 4400 queries

Test #20:

score: 56.3742
Acceptable Answer
time: 83ms
memory: 11376kb

input:

0
1
1
0
0
2
1
1
1
1
1
1
3
2
1
1
2
3
2
0
2
1
2
3
2
0
0
3
1
1
1
2
2
0
1
1
2
1
2
2
1
1
1
1
2
1
2
2
1
1
2
1
2
3
1
0
1
2
2
2
1
1
1
2
1
2
2
1
1
1
0
1
2
1
2
0
2
1
1
2
3
3
2
1
1
0
1
1
2
0
2
1
1
1
1
0
1
1
2
3
2
1
2
0
1
2
2
2
0
0
1
1
1
0
2
1
2
2
2
1
1
1
0
1
3
3
2
3
2
2
1
2
2
2
1
0
1
2
0
2
3
1
2
3
0
2
3
1
1
2
...

output:

? 1 2 3
? 1 2 4
? 2 3 4
? 1 2 5
? 2 3 5
? 3 4 5
? 1 2 6
? 2 3 6
? 3 4 6
? 4 5 6
? 1 2 7
? 2 3 7
? 3 4 7
? 4 5 7
? 5 6 7
? 1 2 8
? 2 3 8
? 3 4 8
? 4 5 8
? 5 6 8
? 4 7 8
? 1 2 9
? 2 3 9
? 3 4 9
? 4 5 9
? 5 6 9
? 6 8 9
? 4 7 9
? 1 2 10
? 2 3 10
? 3 4 10
? 4 5 10
? 5 6 10
? 8 9 10
? 6 8 10
? 7 9 10
? 1 ...

result:

points 0.56374193550 points  0.56374193550 correct 4366 queries