QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117063#6668. Trokutihos_lyric#72.632258 17ms4252kbC++146.9kb2023-06-30 12:44:082024-05-31 18:40:01

Judging History

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

  • [2024-05-31 18:40:01]
  • 评测
  • 测评结果:72.632258
  • 用时:17ms
  • 内存:4252kb
  • [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:44:08]
  • 提交

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];
int Q;
#endif

int 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);
  int s;
#ifdef LOCAL
  ++Q;
  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
  return s;
}

int A[N][N];
void Answer() {
#ifdef LOCAL
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) {
    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
}


map<vector<int>, vector<int>> psss[6];
void small() {
  for (int n = 3; n <= 5; ++n) {
    const int m = n * (n - 1) / 2;
    for (int p = 0; p < 1 << m; ++p) {
      int a[5][5] = {};
      {
        int pos = 0;
        for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) {
          a[u][v] = a[v][u] = p >> pos & 1;
          ++pos;
        }
      }
      vector<int> fs;
      for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) for (int w = v + 1; w < n; ++w) {
        fs.push_back(a[u][v] + a[v][w] + a[w][u]);
      }
      psss[n][fs].push_back(p);
    }
#ifdef LOCAL
    for (const auto &kv : psss[n]) if (kv.second.size() >= 2) {
      cerr << kv.first;
      for (const int p : kv.second) {
        cerr << " ";
        for (int i = 0; i < m; ++i) cerr << ((p >> i) & 1);
      }
      cerr << endl;
    }
#endif
    if (n == 4) {
      for (const auto &kv : psss[n]) {
        for (const int p0 : kv.second) for (const int p1 : kv.second) if (p0 != p1) {
          assert(__builtin_popcount(p0 ^ p1) >= 4);
        }
      }
    }
  }
}

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

void determine(int n, const int us[]) {
  assert(3 <= n); assert(n <= 5);
  vector<int> fs;
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) {
    const int u = us[i], v = us[j], w = us[k];
    int f;
    if (~A[u][v] && ~A[v][w] && ~A[w][u]) {
      f = A[u][v] + A[v][w] + A[w][u];
    } else {
      f = Ask(u, v, w);
    }
    fs.push_back(f);
  }
  auto it = psss[n].find(fs);
  assert(it != psss[n].end());
  {
    int pos = 0;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
      bool ok = true;
      int c = -1;
      for (const int p : it->second) {
        if (!~c) c = p >> pos & 1;
        ok = ok && (c == (p >> pos & 1));
      }
      if (ok) {
        ae(us[i], us[j], c);
      }
      ++pos;
    }
  }
}

constexpr int R = 0;
vector<int> U;
int counter;
void rec(int l, int r) {
  if (r - l >= 3) {
    const int mid = l + (r - l + 1) / 2;
    for (int i = 0; i < mid - l; ++i) for (int j = i + 1; j < mid - l; ++j) {
++counter;
      int u = U[l + i];
      int v = U[l + j];
      int w = U[mid + (i + j) % (r - mid)];
      // swap((xrand() % 2) ? u : v, v);
      // swap((xrand() % 3) ? ((xrand() % 2) ? u : v) : w, w);
      const int f = Ask(u, v, w);
      if (f == 0 || f == 3) {
        ae(u, v, f/3);
        ae(v, w, f/3);
        ae(w, u, f/3);
      } else {
        const int fuv = Ask(R, u, v);
        ae(u, v, fuv - A[R][u] - A[R][v]);
        if (f - A[u][v] == 0 || f - A[u][v] == 2) {
          ae(v, w, (f - A[u][v]) / 2);
          ae(w, u, (f - A[u][v]) / 2);
        } else {
          const int fvw = Ask(R, v, w);
          ae(v, w, fvw - A[R][v] - A[R][w]);
          ae(w, u, f - A[u][v] - A[v][w]);
        }
      }
    }
    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
  
  small();
  
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (u != v) {
    A[u][v] = -1;
  }
  
  {
    vector<int> ss;
    for (int u = 0; u < N; ++u) if (R != u && !~A[R][u]) {
      ss.push_back(u);
    }
    const int ssLen = ss.size();
    for (int h = 0; h < ssLen; h += 4) {
      vector<int> used(N, 0);
      int us[5];
      fill(us, us + 5, -1);
      used[us[0] = R] = 1;
      for (int i = 1; i < 5; ++i) if (h + (i - 1) < ssLen) {
        used[us[i] = ss[h + (i - 1)]] = 1;
      }
      for (int i = 1; i < 5; ++i) if (!~us[i]) {
        for (int u = 0; u < N; ++u) if (!used[u]) {
          used[us[i] = u] = 1;
          break;
        }
        assert(~us[i]);
      }
// pv(us,us+5);
      determine(5, us);
    }
  }
  
  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]);
  }
  rec(0, N - 1);
cerr<<"counter = "<<counter<<endl;
  
  for (int u = 0; u < N; ++u) for (int v = u + 1; v < N; ++v) if (!~A[u][v]) {
    const int res = Ask(R, u, v);
    ae(u, v, res - A[R][u] - A[R][v]);
  }
  
  Answer();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 72.6323
Acceptable Answer

Test #1:

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

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1946 queries

Test #2:

score: 100
Accepted
time: 2ms
memory: 3956kb

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1946 queries

Test #3:

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

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1948 queries

Test #4:

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

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1947 queries

Test #5:

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

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1961 queries

Test #6:

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

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
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 1963 queries

Test #7:

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

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 3386 queries

Test #8:

score: 84.2387
Acceptable Answer
time: 0ms
memory: 4244kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.84238709680 points  0.84238709680 correct 3749 queries

Test #9:

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

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 1.0 points  1.0 correct 3289 queries

Test #10:

score: 73.3548
Acceptable Answer
time: 0ms
memory: 4052kb

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.73354838710 points  0.73354838710 correct 3990 queries

Test #11:

score: 72.7677
Acceptable Answer
time: 0ms
memory: 3924kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.72767741940 points  0.72767741940 correct 4003 queries

Test #12:

score: 74.4839
Acceptable Answer
time: 4ms
memory: 3980kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.74483870970 points  0.74483870970 correct 3965 queries

Test #13:

score: 74.9806
Acceptable Answer
time: 0ms
memory: 3936kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.74980645160 points  0.74980645160 correct 3954 queries

Test #14:

score: 76.2452
Acceptable Answer
time: 5ms
memory: 4048kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.76245161290 points  0.76245161290 correct 3926 queries

Test #15:

score: 73.7613
Acceptable Answer
time: 6ms
memory: 4248kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.73761290320 points  0.73761290320 correct 3981 queries

Test #16:

score: 73.5355
Acceptable Answer
time: 3ms
memory: 4000kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.73535483870 points  0.73535483870 correct 3986 queries

Test #17:

score: 75.5226
Acceptable Answer
time: 17ms
memory: 4244kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.75522580650 points  0.75522580650 correct 3942 queries

Test #18:

score: 72.6323
Acceptable Answer
time: 4ms
memory: 3992kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.72632258060 points  0.72632258060 correct 4006 queries

Test #19:

score: 74.6645
Acceptable Answer
time: 7ms
memory: 4252kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.74664516130 points  0.74664516130 correct 3961 queries

Test #20:

score: 75.3419
Acceptable Answer
time: 0ms
memory: 3988kb

input:

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

output:

? 1 2 3
? 1 2 4
? 1 2 5
? 1 3 4
? 1 3 5
? 1 4 5
? 2 3 4
? 2 3 5
? 2 4 5
? 3 4 5
? 1 6 7
? 1 6 8
? 1 6 9
? 1 7 8
? 1 7 9
? 1 8 9
? 6 7 8
? 6 7 9
? 6 8 9
? 7 8 9
? 1 10 11
? 1 10 12
? 1 10 13
? 1 11 12
? 1 11 13
? 1 12 13
? 10 11 12
? 10 11 13
? 10 12 13
? 11 12 13
? 1 14 15
? 1 14 16
? 1 14 17
? 1 15...

result:

points 0.75341935480 points  0.75341935480 correct 3946 queries