QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117430#6668. Trokutihos_lyric79.812903 90ms7772kbC++147.5kb2023-07-01 07:58:492023-07-01 07:58:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-01 07:58:52]
  • 评测
  • 测评结果:79.812903
  • 用时:90ms
  • 内存:7772kb
  • [2023-07-01 07:58:49]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


// [0, 2^32)
unsigned xrand() {
  static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}

// [a, b]
int xrand(int a, int b) { return a + xrand() % (b - a + 1); }


constexpr int N = 100;

#ifdef LOCAL
int secret[N][N];
#endif

int Q;
int F[N][N][N];
void Ask(int u, int v, int w) {
  assert(0 <= u); assert(u < N);
  assert(0 <= v); assert(v < N);
  assert(0 <= w); assert(w < N);
  assert(u != v); assert(v != w); assert(w != u);
  if (!~F[u][v][w]) {
    ++Q;
    int s;
#ifdef LOCAL
    s = secret[u][v] + secret[v][w] + secret[w][u];
#else
    printf("? %d %d %d\n", u + 1, v + 1, w + 1);
    fflush(stdout);
    scanf("%d", &s);
#endif
    F[u][v][w] = s;
    F[u][w][v] = s;
    F[v][w][u] = s;
    F[v][u][w] = s;
    F[w][u][v] = s;
    F[w][v][u] = s;
  }
}

int A[N][N];
void Answer() {
#ifdef LOCAL
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) {
    if (secret[u][v] != A[u][v]) {
      cerr << "Wrong Answer " << u << " " << v << ": " << secret[u][v] << " " << A[u][v] << endl;
    }
    assert(secret[u][v] == A[u][v]);
  }
  cerr << "Accepted: Q = " << Q << endl;
#else
  puts("!");
  for (int u = 0; u < N; ++u) {
    for (int v = 0; v < N; ++v) {
      printf("%d", A[u][v]);
    }
    puts("");
  }
  fflush(stdout);
#endif
}


bool ae(int u, int v, int c) {
  assert(0 <= u); assert(u < N);
  assert(0 <= v); assert(v < N);
  assert(c == 0 || c == 1);
  bool upd = false;
  if (!~A[u][v]) {
    upd = true;
    A[u][v] = A[v][u] = c;
  }
  assert(A[u][v] == c);
  assert(A[v][u] == c);
  return upd;
}

bool update(int n, const int *us) {
  static constexpr int limN = 5;
  assert(n <= limN);
  bool can[limN][limN][2] = {};
  for (int p = 0; p < 1 << (n*(n-1)/2); ++p) {
    int a[limN][limN] = {};
    {
      int pos = 0;
      for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
        a[i][j] = a[j][i] = p >> pos & 1;
        ++pos;
      }
    }
    bool ok = true;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (~A[us[i]][us[j]]) {
      ok = ok && (A[us[i]][us[j]] == a[i][j]);
    }
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) if (~F[us[i]][us[j]][us[k]]) {
      ok = ok && (F[us[i]][us[j]][us[k]] == a[i][j] + a[j][k] + a[k][i]);
    }
    if (ok) {
      for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
        can[i][j][a[i][j]] = true;
      }
    }
  }
  bool upd = false;
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
    for (int c = 0; c < 2; ++c) if (!can[i][j][c ^ 1]) {
      if (ae(us[i], us[j], c)) {
        upd = true;
      }
    }
  }
  return upd;
}

void update3s() {
  for (; ; ) {
    bool upd = false;
    for (int u = 0; u < N; ++u) for (int v = u + 1; v < N; ++v) for (int w = v + 1; w < N; ++w) {
      const int us[3] = {u, v, w};
      if (update(3, us)) {
        upd = true;
      }
    }
    if (!upd) break;
  }
}

int R;
vector<int> U;

int counter;
void rec(int l, int r) {
  if (r - l >= 3) {
    const int mid = l + (r - l + 0) / 2;
    for (int x = 0; x < mid - l; ++x) for (int y = x + 1; y < mid - l; ++y) {
++counter;
      constexpr int n = 4;
      const int us[n] = {
        R,
        U[l + x],
        U[l + y],
        U[mid + (x + y) % (r - mid)],
      };
      auto check = [&]() -> bool {
        update(n, us);
        for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
          if (!~A[us[i]][us[j]]) {
            return false;
          }
        }
        return true;
      };
      if (!~A[us[1]][us[2]] && !~A[us[2]][us[3]] && !~A[us[3]][us[1]]) {
        Ask(us[1], us[2], us[3]); if (check()) continue;
        Ask(us[0], us[2], us[3]); if (check()) continue;
        Ask(us[0], us[1], us[3]); if (check()) continue;
        assert(false);
      }
      if (~A[us[1]][us[2]] && !~A[us[2]][us[3]] && !~A[us[3]][us[1]]) {
        Ask(us[1], us[2], us[3]); if (check()) continue;
        Ask(us[0], us[2], us[3]); if (check()) continue;
        assert(false);
      }
      if (!~A[us[1]][us[2]] && ~A[us[2]][us[3]] && !~A[us[3]][us[1]]) {
        Ask(us[1], us[2], us[3]); if (check()) continue;
        Ask(us[0], us[1], us[3]); if (check()) continue;
        assert(false);
      }
      if (!~A[us[1]][us[2]] && !~A[us[2]][us[3]] && ~A[us[3]][us[1]]) {
        Ask(us[1], us[2], us[3]); if (check()) continue;
        Ask(us[0], us[2], us[3]); if (check()) continue;
        assert(false);
      }
    }
    rec(mid, r);
  }
}

int main() {
#ifdef LOCAL
  for (int u = 0; u < N; ++u) {
    char buf[N + 1];
    scanf("%s", buf);
    for (int v = 0; v < N; ++v) {
      secret[u][v] = buf[v] - '0';
    }
  }
  for (int u = 0; u < N; ++u) {
    assert(secret[u][u] == 0);
  }
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) {
    assert(secret[u][v] == secret[v][u]);
  }
#endif
  
  memset(A, ~0, sizeof(A));
  for (int u = 0; u < N; ++u) A[u][u] = 0;
  memset(F, ~0, sizeof(F));
  
  R = xrand() % N;
  for (int u = 0; u < N; ++u) if (R != u) U.push_back(u);
  for (int i = 0; i < N - 1; ++i) swap(U[xrand(0, i)], U[i]);
cerr<<"R = "<<R<<", U = "<<U<<endl;
  
  // connect (R, *)
  for (int h = 0; h < N - 1; ) {
    int us[5];
    us[0] = R;
    for (int i = 1; i < 5; ++i) {
      us[i] = U[(h + (i - 1)) % (N - 1)];
    }
cerr<<"us = ";pv(us,us+5);
    for (int n = 3; ; ++n) {
      for (int i = 0; i < n - 1; ++i) for (int j = i + 1; j < n - 1; ++j) {
        Ask(us[i], us[j], us[n - 1]);
        update(n, us);
        bool done = true;
        for (int k = 1; k < n; ++k) {
          done = done && (~A[R][us[k]]);
        }
        if (done) {
          h += (n - 1);
          goto found;
        }
      }
      if (n == 5) {
        assert(false);
      }
    }
   found:{}
  }
  for (const int u : U) {
    assert(~A[R][u]);
  }
cerr<<"Q = "<<Q<<endl;
  update3s();
cerr<<"Q = "<<Q<<endl;
  
  rec(0, N - 1);
cerr<<"Q = "<<Q<<endl;
  update3s();
cerr<<"Q = "<<Q<<endl;
  
  for (int u = 0; u < N; ++u) for (int v = u + 1; v < N; ++v) if (!~A[u][v]) {
    Ask(R, u, v);
    ae(u, v, F[R][u][v] - A[R][u] - A[R][v]);
  }
  
  Answer();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 79.8129
Acceptable Answer

Test #1:

score: 100
Accepted
time: 64ms
memory: 7612kb

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:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1776 queries

Test #2:

score: 100
Accepted
time: 57ms
memory: 7472kb

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:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1776 queries

Test #3:

score: 100
Accepted
time: 50ms
memory: 7728kb

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:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1777 queries

Test #4:

score: 100
Accepted
time: 65ms
memory: 7580kb

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:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1778 queries

Test #5:

score: 100
Accepted
time: 61ms
memory: 7684kb

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
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1791 queries

Test #6:

score: 100
Accepted
time: 55ms
memory: 7536kb

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:

? 13 12 95
? 13 46 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 32 45
? 13 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 13 26 20
? 13 77 83
? 13 25 2
? 13 53 44
? 13 99 58
? 13 74 28
? 13 15 64
? 13 55 10
? 13 6 42
? 13 39 19
? 13 82 9
? 13 5...

result:

points 1.0 points  1.0 correct 1793 queries

Test #7:

score: 100
Accepted
time: 63ms
memory: 7768kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 12 8
? 13 95 8
? 13 30 93
? 13 56 72
? 13 11 57
? 13 11 32
? 13 57 32
? 13 45 43
? 13 45 27
? 13 43 27
? 45 43 27
? 13 71 49
? 13 71 100
? 13 49 100
? 13 75 94
? 13 75 36
? 13 94 36
? 13 50 51
? 13 86 37
? 13 81 78
? 13 85 22
? 13 31 76
? 13 61 29
? 1...

result:

points 1.0 points  1.0 correct 3204 queries

Test #8:

score: 93.2258
Acceptable Answer
time: 61ms
memory: 7752kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 8 30
? 13 8 93
? 13 30 93
? 8 30 93
? 13 8 56
? 13 30 56
? 13 93 56
? 8 30 56
? 13 72 11
? 13 72 57
? 13 11 57
? 13 32 45
? 13 43 27
? 13 43 71
? 13 27 71
? 43 27 71
? 13 43 49
? 13 27 49
? 13 100 75
? 13 100 94
? 13 75 94
? 100 75 94
? 13 100 36
? 13 75 36
? 13 94 36
? 10...

result:

points 0.93225806450 points  0.93225806450 correct 3550 queries

Test #9:

score: 100
Accepted
time: 62ms
memory: 7536kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 13 8 30
? 13 8 93
? 13 30 93
? 13 56 72
? 13 56 11
? 13 72 11
? 13 57 32
? 13 45 43
? 13 45 27
? 13 43 27
? 45 43 27
? 13 71 49
? 13 100 75
? 13 94 36
? 13 94 50
? 13 36 50
? 94 36 50
? 13 51 86
? 13 37 81
? 13 78 85
? 13 22 31
? 13 76 61
? 13 29 26
? 13 20 77
? 13...

result:

points 1.0 points  1.0 correct 3128 queries

Test #10:

score: 84.7355
Acceptable Answer
time: 60ms
memory: 7524kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 8 30
? 13 93 56
? 13 93 72
? 13 56 72
? 93 56 72
? 13 11 57
? 13 11 32
? 13 45 43
? 13 27 71
? 13 27 49
? 13 100 75
? 13 100 94
? 13 75 94
? 100 75 94
? 13 36 50
? 13 51 86
? 13 51 37
? 13 86 37
? 51 86 37
? 13 51 81
? 13 86 81
? 13 37 81
? 51 86 81
? 13 78 85
? 13 78 22
?...

result:

points 0.84735483870 points  0.84735483870 correct 3738 queries

Test #11:

score: 85.6839
Acceptable Answer
time: 52ms
memory: 7584kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 12 8
? 13 95 8
? 13 46 8
? 12 95 8
? 13 30 93
? 13 30 56
? 13 93 56
? 30 93 56
? 13 72 11
? 13 72 57
? 13 11 57
? 72 11 57
? 13 72 32
? 13 11 32
? 13 57 32
? 72 11 32
? 13 45 43
? 13 27 71
? 13 27 49
? 13 71 49
? 13 100 75
? 13 100 94
? 13 36 50
? 13 ...

result:

points 0.85683870970 points  0.85683870970 correct 3717 queries

Test #12:

score: 85.8645
Acceptable Answer
time: 90ms
memory: 7532kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 13 8 30
? 13 8 93
? 13 30 93
? 13 56 72
? 13 11 57
? 13 11 32
? 13 57 32
? 11 57 32
? 13 11 45
? 13 57 45
? 13 43 27
? 13 43 71
? 13 27 71
? 43 27 71
? 13 49 100
? 13 49 75
? 13 100 75
? 49 100 75
? 13 94 36
? 13 94 50
? 13 36 50
? 94 36 50
? 13 51 86
? 13 37 81
? ...

result:

points 0.85864516130 points  0.85864516130 correct 3713 queries

Test #13:

score: 84.9161
Acceptable Answer
time: 79ms
memory: 7772kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 8 30
? 13 93 56
? 13 72 11
? 13 57 32
? 13 57 45
? 13 32 45
? 57 32 45
? 13 43 27
? 13 43 71
? 13 27 71
? 13 49 100
? 13 49 75
? 13 100 75
? 49 100 75
? 13 49 94
? 13 100 94
? 13 75 94
? 13 36 50
? 13 36 51
? 13 50 51
? 36 50 51
? 13 36 86
? 13 50 86
...

result:

points 0.84916129030 points  0.84916129030 correct 3734 queries

Test #14:

score: 79.8129
Acceptable Answer
time: 53ms
memory: 7492kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 8 30
? 13 93 56
? 13 72 11
? 13 57 32
? 13 45 43
? 13 45 27
? 13 43 27
? 13 71 49
? 13 100 75
? 13 100 94
? 13 75 94
? 100 75 94
? 13 36 50
? 13 51 86
? 13 37 81
? 13 37 78
? 13 81 78
? 37 81 78
? 13 85 22
? 13 85 31
? 13 22 31
? 13 76 61
? 13 76 29
?...

result:

points 0.79812903230 points  0.79812903230 correct 3847 queries

Test #15:

score: 84.0129
Acceptable Answer
time: 69ms
memory: 7768kb

input:

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

output:

? 13 12 95
? 13 46 8
? 13 46 30
? 13 8 30
? 46 8 30
? 13 46 93
? 13 8 93
? 13 56 72
? 13 56 11
? 13 72 11
? 56 72 11
? 13 56 57
? 13 72 57
? 13 11 57
? 56 72 57
? 56 11 57
? 13 32 45
? 13 32 43
? 13 45 43
? 13 27 71
? 13 27 49
? 13 71 49
? 27 71 49
? 13 27 100
? 13 75 94
? 13 75 36
? 13 94 36
? 13 5...

result:

points 0.84012903230 points  0.84012903230 correct 3754 queries

Test #16:

score: 85.3677
Acceptable Answer
time: 65ms
memory: 7468kb

input:

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

output:

? 13 12 95
? 13 46 8
? 13 46 30
? 13 8 30
? 46 8 30
? 13 46 93
? 13 8 93
? 13 30 93
? 46 8 93
? 13 56 72
? 13 56 11
? 13 72 11
? 56 72 11
? 13 57 32
? 13 57 45
? 13 32 45
? 13 43 27
? 13 71 49
? 13 71 100
? 13 49 100
? 71 49 100
? 13 71 75
? 13 49 75
? 13 100 75
? 71 49 75
? 13 94 36
? 13 94 50
? 13...

result:

points 0.85367741940 points  0.85367741940 correct 3724 queries

Test #17:

score: 84.8258
Acceptable Answer
time: 71ms
memory: 7580kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 12 8
? 13 95 8
? 13 46 8
? 12 95 8
? 12 46 8
? 13 30 93
? 13 56 72
? 13 56 11
? 13 72 11
? 13 57 32
? 13 57 45
? 13 32 45
? 13 43 27
? 13 43 71
? 13 27 71
? 43 27 71
? 13 43 49
? 13 27 49
? 13 71 49
? 13 100 75
? 13 100 94
? 13 75 94
? 100 75 94
? 13 ...

result:

points 0.84825806450 points  0.84825806450 correct 3736 queries

Test #18:

score: 84.8258
Acceptable Answer
time: 51ms
memory: 7532kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 12 8
? 13 95 8
? 13 46 8
? 12 95 8
? 12 46 8
? 13 30 93
? 13 30 56
? 13 72 11
? 13 57 32
? 13 45 43
? 13 27 71
? 13 27 49
? 13 71 49
? 27 71 49
? 13 100 75
? 13 100 94
? 13 75 94
? 13 36 50
? 13 36 51
? 13 50 51
? 36 50 51
? 13 36 86
? 13 50 86
? 13 3...

result:

points 0.84825806450 points  0.84825806450 correct 3736 queries

Test #19:

score: 83.6065
Acceptable Answer
time: 54ms
memory: 7528kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 12 8
? 13 95 8
? 13 30 93
? 13 30 56
? 13 93 56
? 30 93 56
? 13 72 11
? 13 72 57
? 13 11 57
? 72 11 57
? 13 72 32
? 13 11 32
? 13 57 32
? 72 11 32
? 13 45 43
? 13 45 27
? 13 43 27
? 45 43 27
? 13 71 49
? 13 71 100
? 13 49 100
? 71 49 100
? 13 75 94
? ...

result:

points 0.83606451610 points  0.83606451610 correct 3763 queries

Test #20:

score: 85.9097
Acceptable Answer
time: 68ms
memory: 7528kb

input:

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

output:

? 13 12 95
? 13 12 46
? 13 95 46
? 12 95 46
? 13 8 30
? 13 8 93
? 13 30 93
? 8 30 93
? 13 8 56
? 13 30 56
? 13 72 11
? 13 72 57
? 13 11 57
? 72 11 57
? 13 72 32
? 13 11 32
? 13 57 32
? 72 11 32
? 13 45 43
? 13 27 71
? 13 49 100
? 13 75 94
? 13 75 36
? 13 94 36
? 75 94 36
? 13 50 51
? 13 50 86
? 13 5...

result:

points 0.85909677420 points  0.85909677420 correct 3712 queries