QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117435#6668. Trokutihos_lyric100 ✓18ms7724kbC++147.4kb2023-07-01 09:03:562023-07-01 09:03:59

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 09:03:59]
  • 评测
  • 测评结果:100
  • 用时:18ms
  • 内存:7724kb
  • [2023-07-01 09:03:56]
  • 提交

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); }


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


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

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));
  
  vector<int> U(N);
  for (int u = 0; u < N; ++u) {
    swap(U[xrand(0, u)], U[u] = u);
  }
cerr<<"U = "<<U<<endl;
  
  // determine U[0, 5)
  for (int i = 0; i < 5; ++i) for (int j = i + 1; j < 5; ++j) for (int k = j + 1; k < 5; ++k) {
    Ask(U[i], U[j], U[k]);
  }
  update(5, U.data());
cerr<<__LINE__<<"> Q = "<<Q<<endl;
  
  for (int i = 5; i < N; ++i) {
    // add u
    const int u = U[i];
    
    // connected to (i << 1 | c) <=> A[u][U[j]] == c
    uf.assign((i + 1) << 1, -1);
    auto conn = [&](int j, int k, int d) -> void {
      assert(d == 0 || d == 1);
      connect(j << 1 | 0, k << 1 | (0 ^ d));
      connect(j << 1 | 1, k << 1 | (1 ^ d));
    };
    
    vector<int> js(i);
    for (int j = 0; j < i; ++j) {
      js[j] = j;
    }
    // after 1 iteration, half are A[u][U[j]] == 0/1
    for (; js.size() > 1; ) {
      const int jsLen = js.size();
      for (int x = 0; x < jsLen; ++x) {
        swap(js[xrand(0, x)], js[x]);
      }
// cerr<<"js = "<<js<<endl;
      vector<int> jjs;
      for (int x = 0; x < jsLen; x += 2) {
        if (x + 1 == jsLen) {
          jjs.push_back(js[x]);
          break;
        }
        const int j = js[x], k = js[x + 1];
        Ask(u, U[j], U[k]);
        const int f = F[u][U[j]][U[k]] - A[U[j]][U[k]];
// cerr<<"  "<<j<<" "<<k<<": "<<f<<endl;
        if (f == 0 || f == 2) {
          conn(j, i, f / 2);
          conn(k, i, f / 2);
        } else {
          // A[u][U[j]] != A[u][U[k]]
          conn(j, k, 1);
          jjs.push_back(xrand(0, 1) ? j : k);
        }
      }
      js = jjs;
    }
// cerr<<"js = "<<js<<endl;
    if (js.size() == 1) {
      const int j = js[0];
      for (int k = 0; k < i; ++k) if (j != k) {
        for (int c = 0; c < 2; ++c) {
          if (root(k << 1) == root(i << 1 | c)) {
            Ask(u, U[j], U[k]);
            const int f = F[u][U[j]][U[k]] - A[U[j]][U[k]];
            conn(j, i, f - c);
            goto found;
          }
        }
      }
      for (int k = 0; k < i; ++k) if (j != k) {
        if (root(j << 1) == root(k << 1)) {
          Ask(u, U[j], U[k]);
          const int f = F[u][U[j]][U[k]] - A[U[j]][U[k]];
          assert(f == 0 || f == 2);
          if (f == 0 || f == 2) {
            conn(j, i, f / 2);
            conn(k, i, f / 2);
          }
          goto found;
        }
      }
      assert(false);
     found:{}
    }
    
    for (int j = 0; j < i; ++j) {
      for (int c = 0; c < 2; ++c) {
        if (root(j << 1) == root(i << 1 | c)) {
          ae(u, U[j], c);
        }
      }
      assert(~A[u][U[j]]);
    }
  }
cerr<<__LINE__<<"> Q = "<<Q<<endl;
  
  Answer();
  return 0;
}

详细

Subtask #1:

score: 100
Accepted

Test #1:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2504 queries

Test #2:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2504 queries

Test #3:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2505 queries

Test #4:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2505 queries

Test #5:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2511 queries

Test #6:

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

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:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 5 94 95
? 5 93 38
? 5 51 15
? 5 19 15
? 20 95 51
? 20 19 94
? 20 15 5
? 20 93 38
? 64 94 19
? 64 95 38
? 64 20 93
? 64 51 ...

result:

points 1.0 points  1.0 correct 2510 queries

Test #7:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 19 38
? 51 93 95
? 51 94 15
? 51 15 93
? 5 95 51
? 5 19 94
? 5 15 38
? 5 93 15
? 20 15 5
? 20 93 94
? 20 38 19
? 20 95 51
? 20 93 15
? 64 15 19
? 64 51 ...

result:

points 1.0 points  1.0 correct 3103 queries

Test #8:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 95 15 19
? 51 93 38
? 51 15 19
? 51 95 94
? 5 38 93
? 5 51 94
? 5 95 15
? 5 19 15
? 20 95 38
? 20 93 5
? 20 19 51
? 20 94 15
? 20 51 15
? 64 95 94
? 64 19 ...

result:

points 1.0 points  1.0 correct 3214 queries

Test #9:

score: 100
Accepted
time: 15ms
memory: 7628kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 95 93 19
? 51 38 93
? 51 19 95
? 51 15 94
? 5 51 93
? 5 38 95
? 5 94 19
? 5 15 19
? 20 93 38
? 20 94 15
? 20 19 95
? 20 51 5
? 20 94 95
? 64 15 19
? 64 51 ...

result:

points 1.0 points  1.0 correct 3065 queries

Test #10:

score: 100
Accepted
time: 13ms
memory: 7672kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 95 93 19
? 51 38 93
? 51 19 95
? 51 15 94
? 51 94 93
? 51 19 15
? 5 93 19
? 5 15 94
? 5 38 95
? 5 19 15
? 5 38 51
? 5 38 15
? 20 19 94
? 20 51 38
? 20 15 9...

result:

points 1.0 points  1.0 correct 3340 queries

Test #11:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 51 93 15
? 5 94 19
? 5 93 51
? 5 95 38
? 5 15 38
? 5 15 19
? 20 95 38
? 20 93 5
? 20 19 51
? 20 94 15
? 20 15 19
? 64 95 9...

result:

points 1.0 points  1.0 correct 3305 queries

Test #12:

score: 100
Accepted
time: 16ms
memory: 7700kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 51 19 38
? 51 93 95
? 51 94 15
? 51 94 19
? 5 51 93
? 5 38 95
? 5 94 19
? 5 51 95
? 5 51 15
? 5 51 19
? 20 5 19
? 20 95 38
? 20 93 94
? 20 51 15
? 20 95 93...

result:

points 1.0 points  1.0 correct 3291 queries

Test #13:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 51 19 38
? 51 93 95
? 51 94 15
? 51 93 15
? 5 51 93
? 5 38 95
? 5 94 19
? 5 38 19
? 5 15 19
? 20 51 94
? 20 15 5
? 20 93 95
? 20 19 38
? 64 38 95
? 64 93 5...

result:

points 1.0 points  1.0 correct 3316 queries

Test #14:

score: 100
Accepted
time: 4ms
memory: 7644kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 95 15 19
? 51 95 38
? 51 19 94
? 51 15 93
? 51 94 15
? 5 93 94
? 5 38 51
? 5 19 15
? 5 38 15
? 5 95 15
? 20 95 94
? 20 19 5
? 20 93 51
? 20 15 38
? 20 19 1...

result:

points 1.0 points  1.0 correct 3314 queries

Test #15:

score: 100
Accepted
time: 15ms
memory: 7724kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 95 93 15
? 51 38 93
? 51 19 95
? 51 15 94
? 5 51 93
? 5 38 95
? 5 94 19
? 5 15 94
? 5 15 38
? 20 94 19
? 20 95 38
? 20 15 93
? 20 51 5
? 20 51 15
? 64 15 3...

result:

points 1.0 points  1.0 correct 3310 queries

Test #16:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 19
? 95 93 15
? 51 38 93
? 51 19 95
? 51 15 94
? 51 94 19
? 5 38 93
? 5 51 94
? 5 95 15
? 5 93 19
? 20 94 19
? 20 95 38
? 20 15 93
? 20 51 5
? 20 51 94
? 20 94 ...

result:

points 1.0 points  1.0 correct 3289 queries

Test #17:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 51 93 94
? 5 51 93
? 5 38 95
? 5 94 19
? 5 15 94
? 20 15 5
? 20 93 94
? 20 38 19
? 20 95 51
? 20 38 15
? 64 94 95
? 64 51 ...

result:

points 1.0 points  1.0 correct 3359 queries

Test #18:

score: 100
Accepted
time: 18ms
memory: 7628kb

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 93 38
? 51 95 15
? 51 19 94
? 51 15 19
? 51 93 15
? 5 94 95
? 5 93 15
? 5 19 38
? 5 95 51
? 5 95 15
? 20 93 94
? 20 38 5
? 20 15 51
? 20 95 19
? 20 94 5...

result:

points 1.0 points  1.0 correct 3361 queries

Test #19:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 51 19 38
? 51 93 95
? 51 94 15
? 51 94 19
? 5 51 93
? 5 38 95
? 5 94 19
? 5 15 38
? 5 15 19
? 20 94 19
? 20 95 38
? 20 15 93
? 20 51 5
? 20 5 94
? 20 95 15...

result:

points 1.0 points  1.0 correct 3345 queries

Test #20:

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

input:

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

output:

? 15 19 94
? 15 19 38
? 15 19 93
? 15 94 38
? 15 94 93
? 15 38 93
? 19 94 38
? 19 94 93
? 19 38 93
? 94 38 93
? 95 94 15
? 95 38 19
? 95 93 15
? 95 93 19
? 51 38 93
? 51 19 95
? 51 15 94
? 51 94 19
? 5 38 93
? 5 51 94
? 5 95 15
? 5 93 15
? 5 19 15
? 20 93 94
? 20 38 5
? 20 15 51
? 20 95 19
? 20 19 1...

result:

points 1.0 points  1.0 correct 3308 queries