QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117208#6668. TrokutiIrisu100 ✓29ms8116kbC++176.4kb2023-06-30 16:58:472023-06-30 16:58:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 16:58:48]
  • 评测
  • 测评结果:100
  • 用时:29ms
  • 内存:8116kb
  • [2023-06-30 16:58:47]
  • 提交

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<50&&j>=50;
//    rep(i,1,n)rep(j,i+1,n)mp[i][j]=mp[j][i]=Rnd()%100<0;
  }
  
  {
    int c=0;
    rep(i,1,n)rep(j,1,i-1)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);
    }
  };
  int eq=-1;
  rep(s,3,n){
    vector<pii>lef;
    rep(a,1,s-1)rep(b,a+1,s-1){
      lef.pb({a,b});
    }
    shuffle(ALL(lef),Rnd);
    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(eq==-1)eq=v;
      else if(eq!=v)eq=-2;
      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;
      }
    }
    if(s==n||(s>20&&rk==s*(s-1)/2)||((s>20)&&(eq==-2||eq==1||eq==2))){
      static bit a[20000];
      int tot=0;
      int L=s*(s-1)/2;
      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(L+1);
        }
      }
      rep(i,1,L)if(buk[i]!=-1){
        tot++;
        a[tot].set(i);
        if(buk[i])a[tot].set(L+1);
      }
      rep(i,1,L){
        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,L,1){
        assert(a[i][i]);
        buk[i]=a[i][L+1];
        if(a[i][L+1]){
          rep(j,1,i-1)if(a[j][i]){
            a[j].flip(L+1);
          }
        }
      }
      
    //  printf("!%d, %d\n",rk,use_q);
      
      rep(t,s+1,n){
        vector<pii>o;
        int lst=-1;
        rep(i,1,t-1){
          if(lst==-1){
            lst=i;continue;
          }
          int v=ask(lst,i,t);
          if(v==0||v==3){
            buk[tid[lst][i]]=buk[tid[i][t]]=buk[tid[lst][t]]=v>0;
            lst=-1;
          }else if(v%2==buk[tid[lst][i]]){
            buk[tid[i][t]]=buk[tid[lst][t]]=!(v%2);
            lst=-1;
          }else{
            o.pb({lst,i});
            lst=i;
          }
        }
        reverse(ALL(o));
        for(auto[a,b]:o)if(buk[tid[b][t]]!=-1)buk[tid[a][t]]=!buk[tid[b][t]];
        rep(lst,1,t-1)if(buk[tid[lst][t]]==-1){
          rep(i,1,t-1)if(i!=lst){
            bool can=1;
            for(auto[a,b]:o){
              if(lst==a)can&=i!=b;
              if(lst==b)can&=i!=a;
            }
            if(!can)continue;
            assert(buk[tid[i][t]]!=-1);
            int v=ask(lst,i,t);
            buk[tid[lst][t]]=v-buk[tid[lst][i]]-buk[tid[i][t]];
            lst=-1;
            break;
          }
          if(lst==-1)break;
        }
        rep(_,0,o.size()){
          for(auto[a,b]:o)if(buk[tid[b][t]]!=-1)buk[tid[a][t]]=!buk[tid[b][t]];
          for(auto[a,b]:o)if(buk[tid[a][t]]!=-1)buk[tid[b][t]]=!buk[tid[a][t]];
        }
      }
      break;
    }
  }
  
  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: 100
Accepted

Test #1:

score: 100
Accepted
time: 1ms
memory: 6052kb

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:

? 14 65 40
? 65 40 27
? 14 40 27
? 40 27 9
? 65 40 9
? 14 27 9
? 27 9 53
? 14 9 53
? 40 9 53
? 65 9 53
? 40 27 84
? 40 53 84
? 14 27 84
? 14 9 84
? 65 27 84
? 40 27 24
? 27 53 24
? 65 40 24
? 14 53 24
? 40 9 24
? 40 84 24
? 65 9 95
? 65 40 95
? 65 24 95
? 65 84 95
? 14 53 95
? 27 9 95
? 40 9 42
? 24...

result:

points 1.0 points  1.0 correct 2550 queries

Test #2:

score: 100
Accepted
time: 9ms
memory: 5996kb

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:

? 65 8 2
? 65 2 32
? 8 2 32
? 8 2 20
? 65 2 20
? 2 32 20
? 65 2 75
? 65 8 75
? 2 20 75
? 8 32 75
? 8 20 18
? 65 8 18
? 20 75 18
? 65 2 18
? 2 32 18
? 32 75 87
? 20 75 87
? 2 20 87
? 2 18 87
? 65 2 87
? 8 32 87
? 8 18 11
? 20 75 11
? 65 2 11
? 32 75 11
? 32 87 11
? 65 11 100
? 75 18 100
? 32 87 100
?...

result:

points 1.0 points  1.0 correct 2543 queries

Test #3:

score: 100
Accepted
time: 12ms
memory: 8012kb

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:

? 58 33 24
? 58 33 1
? 58 24 1
? 58 1 86
? 58 33 86
? 33 24 86
? 24 86 16
? 58 86 16
? 33 24 16
? 1 86 16
? 58 24 45
? 1 16 45
? 33 1 45
? 86 16 45
? 58 1 99
? 58 45 99
? 33 16 99
? 1 86 99
? 58 24 99
? 24 45 95
? 58 99 95
? 33 24 95
? 33 1 95
? 58 86 95
? 58 16 95
? 58 16 49
? 58 33 49
? 33 24 49
?...

result:

points 1.0 points  1.0 correct 2547 queries

Test #4:

score: 100
Accepted
time: 7ms
memory: 6048kb

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:

? 10 44 89
? 10 89 93
? 10 44 93
? 44 93 88
? 10 89 88
? 10 44 30
? 10 88 30
? 44 89 30
? 93 88 30
? 10 44 69
? 10 30 69
? 89 30 69
? 89 93 69
? 93 88 69
? 89 93 5
? 44 93 5
? 93 69 5
? 10 44 5
? 44 30 5
? 88 69 5
? 89 88 78
? 93 88 78
? 93 30 78
? 30 69 78
? 10 69 78
? 44 88 78
? 88 5 78
? 89 93 63...

result:

points 1.0 points  1.0 correct 2550 queries

Test #5:

score: 100
Accepted
time: 0ms
memory: 5992kb

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:

? 90 97 36
? 90 97 13
? 90 36 13
? 36 13 88
? 97 13 88
? 90 36 88
? 90 36 41
? 90 88 41
? 90 13 41
? 97 36 41
? 90 88 50
? 36 13 50
? 90 41 50
? 97 36 50
? 90 36 44
? 90 13 44
? 41 50 44
? 88 41 44
? 97 41 44
? 90 44 78
? 97 50 78
? 36 13 78
? 13 41 78
? 88 41 78
? 97 50 72
? 97 41 72
? 13 41 72
? 9...

result:

points 1.0 points  1.0 correct 2552 queries

Test #6:

score: 100
Accepted
time: 5ms
memory: 5968kb

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:

? 2 90 45
? 2 90 3
? 2 45 3
? 2 90 43
? 90 45 43
? 2 3 43
? 2 90 49
? 90 3 49
? 2 43 49
? 90 45 49
? 45 3 60
? 90 3 60
? 2 49 60
? 2 43 60
? 45 43 96
? 90 43 96
? 49 60 96
? 3 43 96
? 2 49 96
? 45 49 82
? 45 60 82
? 2 90 82
? 43 96 82
? 3 43 82
? 3 60 95
? 2 45 95
? 45 82 95
? 43 96 95
? 90 49 95
? ...

result:

points 1.0 points  1.0 correct 2543 queries

Test #7:

score: 100
Accepted
time: 8ms
memory: 5976kb

input:

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

output:

? 9 40 71
? 9 40 25
? 9 71 25
? 9 40 42
? 71 25 42
? 40 71 42
? 40 42 62
? 9 40 62
? 71 42 62
? 25 42 62
? 9 40 79
? 9 62 79
? 9 25 79
? 71 62 79
? 9 42 79
? 9 71 19
? 9 79 19
? 40 71 19
? 40 62 19
? 71 42 19
? 25 79 19
? 9 25 33
? 79 19 33
? 25 19 33
? 9 62 33
? 42 19 33
? 71 42 33
? 40 19 33
? 40 ...

result:

points 1.0 points  1.0 correct 3130 queries

Test #8:

score: 100
Accepted
time: 3ms
memory: 8020kb

input:

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

output:

? 6 4 9
? 6 4 91
? 4 9 91
? 6 91 27
? 4 9 27
? 9 91 27
? 9 27 66
? 6 9 66
? 4 91 66
? 4 27 66
? 91 27 69
? 9 91 69
? 6 9 69
? 6 66 69
? 6 4 69
? 91 66 34
? 4 27 34
? 27 66 34
? 9 91 34
? 6 27 34
? 6 69 34
? 4 69 86
? 91 27 86
? 9 27 86
? 91 66 86
? 6 9 86
? 69 34 86
? 4 69 50
? 27 69 50
? 6 91 50
? ...

result:

points 1.0 points  1.0 correct 3300 queries

Test #9:

score: 100
Accepted
time: 1ms
memory: 6000kb

input:

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

output:

? 82 25 72
? 82 25 12
? 82 72 12
? 25 12 1
? 25 72 1
? 82 12 1
? 72 1 96
? 25 72 96
? 82 1 96
? 72 12 96
? 72 1 61
? 82 25 61
? 82 12 61
? 12 1 61
? 72 96 61
? 25 12 89
? 1 96 89
? 82 61 89
? 72 61 89
? 96 61 89
? 72 96 44
? 1 89 44
? 96 61 44
? 12 61 44
? 25 72 44
? 82 61 44
? 25 44 80
? 96 44 80
?...

result:

points 1.0 points  1.0 correct 3133 queries

Test #10:

score: 100
Accepted
time: 17ms
memory: 6032kb

input:

0
2
2
2
2
2
0
2
2
2
0
2
0
2
2
2
2
2
2
2
2
0
2
2
2
2
0
2
2
2
0
2
2
2
2
2
0
2
2
2
0
2
2
2
2
2
0
2
2
0
2
2
2
2
0
2
0
0
2
2
2
2
2
2
0
2
0
0
2
2
0
0
0
2
2
2
2
2
2
2
2
2
2
2
0
2
0
2
2
2
2
0
2
2
2
2
2
2
2
0
2
0
2
2
2
0
2
2
2
2
2
0
2
2
2
0
0
2
2
2
2
0
2
2
2
0
2
2
2
0
2
2
2
2
2
0
2
2
0
2
2
2
2
0
2
2
2
2
2
2
...

output:

? 26 48 3
? 48 3 73
? 26 3 73
? 48 3 79
? 26 73 79
? 48 73 79
? 73 79 56
? 26 73 56
? 3 73 56
? 48 73 56
? 26 3 40
? 48 73 40
? 26 48 40
? 3 79 40
? 48 56 40
? 79 40 58
? 26 79 58
? 26 48 58
? 3 73 58
? 26 73 58
? 56 40 58
? 48 40 33
? 26 73 33
? 26 56 33
? 48 58 33
? 79 56 33
? 26 3 33
? 79 40 81
?...

result:

points 1.0 points  1.0 correct 3275 queries

Test #11:

score: 100
Accepted
time: 5ms
memory: 6008kb

input:

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

output:

? 70 47 34
? 70 34 58
? 47 34 58
? 47 58 94
? 70 58 94
? 34 58 94
? 47 94 91
? 70 94 91
? 70 34 91
? 34 58 91
? 34 58 19
? 70 34 19
? 47 94 19
? 58 91 19
? 47 58 19
? 70 34 51
? 47 91 51
? 34 58 51
? 47 19 51
? 94 91 51
? 34 19 51
? 34 51 93
? 34 91 93
? 34 58 93
? 94 91 93
? 70 19 93
? 47 51 93
? 7...

result:

points 1.0 points  1.0 correct 3380 queries

Test #12:

score: 100
Accepted
time: 11ms
memory: 5976kb

input:

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

output:

? 9 16 80
? 9 16 22
? 16 80 22
? 80 22 98
? 9 16 98
? 9 80 98
? 16 80 46
? 22 98 46
? 80 98 46
? 9 98 46
? 9 46 30
? 80 46 30
? 9 22 30
? 16 98 30
? 16 80 30
? 9 46 26
? 22 46 26
? 46 30 26
? 22 98 26
? 16 30 26
? 80 30 26
? 46 26 11
? 16 98 11
? 22 30 11
? 9 98 11
? 16 46 11
? 22 46 11
? 80 30 11
?...

result:

points 1.0 points  1.0 correct 3346 queries

Test #13:

score: 100
Accepted
time: 5ms
memory: 6008kb

input:

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

output:

? 91 21 51
? 91 51 10
? 91 21 10
? 21 51 78
? 91 21 78
? 51 10 78
? 91 21 72
? 91 78 72
? 51 10 72
? 91 10 72
? 91 10 43
? 21 10 43
? 51 10 43
? 21 78 43
? 78 72 43
? 51 78 25
? 10 78 25
? 78 43 25
? 51 72 25
? 91 43 25
? 21 10 25
? 78 25 80
? 21 25 80
? 10 78 80
? 51 25 80
? 91 25 80
? 10 72 80
? 4...

result:

points 1.0 points  1.0 correct 3348 queries

Test #14:

score: 100
Accepted
time: 6ms
memory: 5976kb

input:

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

output:

? 53 9 48
? 53 48 16
? 53 9 16
? 9 48 95
? 53 48 95
? 48 16 95
? 53 48 82
? 16 95 82
? 9 48 82
? 9 16 11
? 48 82 11
? 53 82 11
? 9 48 11
? 9 95 11
? 53 82 32
? 53 11 32
? 16 11 32
? 48 82 32
? 9 82 32
? 16 95 32
? 53 32 96
? 95 82 96
? 9 16 96
? 82 11 96
? 16 82 96
? 16 32 96
? 48 32 96
? 82 96 41
?...

result:

points 1.0 points  1.0 correct 3351 queries

Test #15:

score: 100
Accepted
time: 6ms
memory: 5976kb

input:

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

output:

? 27 1 31
? 27 1 20
? 27 31 20
? 1 31 43
? 27 1 43
? 27 20 43
? 27 31 87
? 1 20 87
? 27 1 87
? 20 43 87
? 27 87 76
? 1 20 76
? 31 20 76
? 20 43 76
? 27 43 76
? 43 87 24
? 31 43 24
? 27 76 24
? 1 76 24
? 27 87 24
? 20 87 24
? 27 20 62
? 20 76 62
? 1 20 62
? 27 43 62
? 1 31 62
? 76 24 62
? 1 87 62
? 3...

result:

points 1.0 points  1.0 correct 3363 queries

Test #16:

score: 100
Accepted
time: 9ms
memory: 5972kb

input:

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

output:

? 65 77 33
? 65 77 87
? 65 33 87
? 65 33 35
? 65 87 35
? 65 77 35
? 65 33 84
? 77 33 84
? 65 35 84
? 33 87 84
? 35 84 24
? 33 87 24
? 65 84 24
? 33 35 24
? 77 84 24
? 87 84 41
? 33 24 41
? 87 35 41
? 77 84 41
? 65 35 41
? 77 24 41
? 65 41 26
? 65 84 26
? 33 35 26
? 65 87 26
? 77 35 26
? 24 41 26
? 6...

result:

points 1.0 points  1.0 correct 3381 queries

Test #17:

score: 100
Accepted
time: 11ms
memory: 8116kb

input:

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

output:

? 19 49 75
? 49 75 25
? 19 75 25
? 19 75 57
? 19 49 57
? 19 25 57
? 75 57 34
? 49 75 34
? 49 25 34
? 19 49 34
? 49 57 80
? 19 34 80
? 57 34 80
? 75 34 80
? 25 34 80
? 25 80 17
? 75 57 17
? 49 57 17
? 57 80 17
? 57 34 17
? 19 34 17
? 75 57 100
? 25 57 100
? 57 34 100
? 19 25 100
? 57 17 100
? 57 80 1...

result:

points 1.0 points  1.0 correct 3351 queries

Test #18:

score: 100
Accepted
time: 11ms
memory: 5988kb

input:

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

output:

? 44 3 97
? 44 97 13
? 3 97 13
? 3 13 26
? 44 13 26
? 3 97 26
? 3 26 12
? 44 3 12
? 44 97 12
? 97 13 12
? 3 26 68
? 13 12 68
? 44 12 68
? 97 26 68
? 44 3 68
? 26 68 88
? 44 12 88
? 13 12 88
? 97 13 88
? 44 26 88
? 3 97 88
? 3 26 32
? 97 88 32
? 44 13 32
? 97 68 32
? 97 13 32
? 44 26 32
? 12 88 32
? ...

result:

points 1.0 points  1.0 correct 3338 queries

Test #19:

score: 100
Accepted
time: 29ms
memory: 6040kb

input:

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

output:

? 44 9 27
? 9 27 46
? 44 27 46
? 44 46 74
? 9 27 74
? 44 9 74
? 9 27 12
? 44 9 12
? 9 46 12
? 27 74 12
? 44 9 75
? 9 12 75
? 27 74 75
? 27 12 75
? 27 46 75
? 46 75 41
? 27 12 41
? 27 74 41
? 44 12 41
? 46 12 41
? 9 75 41
? 46 74 53
? 74 75 53
? 12 41 53
? 44 27 53
? 27 46 53
? 9 12 53
? 9 75 48
? 46...

result:

points 1.0 points  1.0 correct 3363 queries

Test #20:

score: 100
Accepted
time: 22ms
memory: 6008kb

input:

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

output:

? 84 12 96
? 84 12 48
? 12 96 48
? 84 12 9
? 96 48 9
? 84 96 9
? 12 48 72
? 12 9 72
? 84 96 72
? 12 96 72
? 84 72 46
? 84 96 46
? 48 72 46
? 84 12 46
? 84 9 46
? 48 9 19
? 9 46 19
? 96 48 19
? 72 46 19
? 12 72 19
? 84 46 19
? 12 46 3
? 9 46 3
? 12 72 3
? 84 12 3
? 48 19 3
? 84 19 3
? 96 19 3
? 48 9 ...

result:

points 1.0 points  1.0 correct 3359 queries