QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#600360#9432. Permutationhos_lyricAC ✓281ms4160kbC++144.3kb2024-09-29 16:06:542024-09-29 16:06:54

Judging History

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

  • [2024-09-29 16:06:54]
  • 评测
  • 测评结果:AC
  • 用时:281ms
  • 内存:4160kb
  • [2024-09-29 16:06:54]
  • 提交

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 <random>
#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; }
#define COLOR(s) ("\x1b[" s "m")


int N;

#ifdef LOCAL
vector<int> secret;
int Q;
vector<int> qs;
void gen(int seed) {
  mt19937_64 rng(seed);
  secret.resize(N);
  for (int i = 0; i < N; ++i) swap(secret[rng() % (i + 1)], secret[i] = i + 1);
  Q = 0;
  qs.assign(11, 0);
}
#endif

// answer if (!~depth)
int ask(int depth, const vector<int> &as) {
#ifdef LOCAL
  if (~depth) {
    ++Q;
    ++qs[depth];
  }
  int ret = 0;
  for (int i = 0; i < N; ++i) if (secret[i] == as[i]) ++ret;
// cerr<<COLOR("33")<<as<<": "<<ret<<COLOR()<<endl;
  if (!~depth) {
    assert(ret == N);
  }
  return ret;
#else
  printf("%d", (~depth) ? 0 : 1);
  for (int i = 0; i < N; ++i) printf(" %d", as[i]);
  puts("");
  fflush(stdout);
  if (!~depth) {
    return N;
  }
  int ret;
  scanf("%d", &ret);
  return ret;
#endif
}

#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
vector<int> ans;
void rec(int depth, int l, int r, vector<int> xs) {
// cerr<<"[rec] "<<depth<<" "<<l<<" "<<r<<" "<<xs<<endl;
  assert(r - l == (int)xs.size());
  if (l + 1 == r) {
    ans[l] = xs[0];
  } else {
    const int m = (l + r) / 2;
    for (int j = 0; j < r - l; ++j) swap(xs[rng() % (j + 1)], xs[j]);
// cerr<<"  xs = "<<xs<<endl;
    vector<int> sides(r - l, -1);
    vector<pair<int, int>> same;
    queue<int> que;
    for (int j = 0; j < r - l; ++j) que.push(j);
    for (; que.size() >= 2; ) {
      const int j0 = que.front(); que.pop();
      const int j1 = que.front(); que.pop();
      vector<int> as(N, xs[j0]);
      for (int i = m; i < r; ++i) as[i] = xs[j1];
      const int res = ask(depth, as);
      if (res == 0) {
        sides[j0] = 1;
        sides[j1] = 0;
      } else if (res == 1) {
        same.emplace_back(j0, j1);
        que.push(j0);
      } else if (res == 2) {
        sides[j0] = 0;
        sides[j1] = 1;
      } else {
        assert(false);
      }
    }
    reverse(same.begin(), same.end());
    for (const auto &e : same) sides[e.second] = sides[e.first];
    if (que.size()) {
      int cnt[2] = {};
      for (int j = 0; j < r - l; ++j) if (~sides[j]) ++cnt[sides[j]];
// cerr<<"  sides = "<<sides<<", cnt = ";pv(cnt,cnt+2);
      assert((cnt[0] == m - l) + (cnt[1] == r - m) == 1);
      const int s = (cnt[0] == m - l) ? 1 : 0;
      for (int j = 0; j < r - l; ++j) if (!~sides[j]) sides[j] = s;
    }
    vector<int> xss[2];
    for (int j = 0; j < r - l; ++j) xss[sides[j]].push_back(xs[j]);
    rec(depth + 1, l, m, xss[0]);
    rec(depth + 1, m, r, xss[1]);
  }
}
void solve() {
  ans.assign(N, -1);
  vector<int> xs(N);
  for (int x = 1; x <= N; ++x) xs[x - 1] = x;
  rec(0, 0, N, xs);
  ask(-1, ans);
}

#ifdef LOCAL
void stress() {
  for (N = 1; N <= 1000; N *= 10) {
    for (int seed = 0; seed < 10; ++seed) {
      gen(seed);
// cerr<<"secret = "<<secret<<endl;
      solve();
      cerr << "N = " << N << ": Q = " << Q << ", qs = " << qs << endl;
    }
  }
}
#endif

int main() {
  // stress();
  
  scanf("%d", &N);
  solve();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
0
2
1
2
2

output:

0 1 1 4 4 4
0 5 5 3 3 3
0 3 4 3 3 3
0 1 1 1 5 5
0 2 2 2 1 1
0 1 1 1 1 5
1 3 4 2 1 5

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 269ms
memory: 3868kb

input:

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

output:

0 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 8...

result:

ok Accepted

Test #3:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

1

output:

1 1

result:

ok Accepted

Test #4:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

3
2
0

output:

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

result:

ok Accepted

Test #6:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

4
2
2
0
0

output:

0 4 4 1 1
0 3 3 2 2
0 4 3 4 4
0 1 1 1 2
1 3 4 2 1

result:

ok Accepted

Test #7:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

6
1
1
0
2
0
2
1
2
0

output:

0 3 3 3 4 4 4
0 1 1 1 5 5 5
0 6 6 6 2 2 2
0 3 3 3 1 1 1
0 2 3 3 2 2 2
0 4 4 2 4 4 4
0 6 6 6 6 5 5
0 1 1 1 1 6 6
0 5 5 5 5 5 6
1 3 4 2 1 6 5

result:

ok Accepted

Test #8:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

7
0
0
2
0
0
0
0
0
2

output:

0 4 4 4 7 7 7 7
0 5 5 5 2 2 2 2
0 3 3 3 1 1 1 1
0 7 3 3 7 7 7 7
0 2 2 7 2 2 2 2
0 5 5 5 5 5 6 6
0 4 4 4 4 4 1 1
0 6 6 6 6 1 6 6
0 5 5 5 5 5 5 4
1 3 7 2 1 6 5 4

result:

ok Accepted

Test #9:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

8
2
1
0
1
2
0
2
2
2
0
2
0
0

output:

0 1 1 1 1 8 8 8 8
0 3 3 3 3 2 2 2 2
0 6 6 6 6 7 7 7 7
0 4 4 4 4 5 5 5 5
0 3 3 3 3 4 4 4 4
0 2 2 7 7 2 2 2 2
0 3 3 1 1 3 3 3 3
0 3 7 3 3 3 3 3 3
0 2 2 2 1 2 2 2 2
0 4 4 4 4 4 4 5 5
0 6 6 6 6 6 6 8 8
0 5 5 5 5 5 6 5 5
0 8 8 8 8 8 8 8 4
1 3 7 2 1 6 5 4 8

result:

ok Accepted

Test #10:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

9
0
0
1
0
2
0
2
0
2
1
1
1
2
2
2
2

output:

0 9 9 9 9 3 3 3 3 3
0 4 4 4 4 1 1 1 1 1
0 8 8 8 8 6 6 6 6 6
0 5 5 5 5 2 2 2 2 2
0 7 7 7 7 8 8 8 8 8
0 2 2 3 3 2 2 2 2 2
0 7 7 1 1 7 7 7 7 7
0 7 3 7 7 7 7 7 7 7
0 2 2 2 1 2 2 2 2 2
0 8 8 8 8 8 8 6 6 6
0 9 9 9 9 9 9 5 5 5
0 4 4 4 4 4 4 8 8 8
0 9 9 9 9 9 9 4 4 4
0 9 9 9 9 9 5 9 9 9
0 4 4 4 4 4 4 4 8 8
...

result:

ok Accepted

Test #11:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

10
0
0
1
2
1
2
2
0
2
1
2
2
0
1
2
0
2
2

output:

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

result:

ok Accepted

Test #12:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

11
1
1
1
2
0
2
2
1
1
0
0
2
0
2
0
2
0
0
1
2
2

output:

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

result:

ok Accepted

Test #13:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

12
1
0
1
2
1
1
1
1
0
2
0
0
2
0
0
2
1
0
1
0
0
0
0
2

output:

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

result:

ok Accepted

Test #14:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

13
1
1
2
2
1
1
1
0
2
2
2
0
1
2
2
2
0
0
1
0
2
2
2
2
0
2
0

output:

0 3 3 3 3 3 3 11 11 11 11 11 11 11
0 2 2 2 2 2 2 8 8 8 8 8 8 8
0 10 10 10 10 10 10 6 6 6 6 6 6 6
0 7 7 7 7 7 7 12 12 12 12 12 12 12
0 5 5 5 5 5 5 13 13 13 13 13 13 13
0 9 9 9 9 9 9 1 1 1 1 1 1 1
0 4 4 4 4 4 4 3 3 3 3 3 3 3
0 2 2 2 2 2 2 5 5 5 5 5 5 5
0 9 9 9 9 9 9 4 4 4 4 4 4 4
0 13 13 13 1 1 1 13 1...

result:

ok Accepted

Test #15:

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

input:

14
1
2
1
1
2
1
0
0
0
2
2
0
1
2
0
0
0
0
0
1
1
0
1
2
0
2
2
0
2
0

output:

0 8 8 8 8 8 8 8 6 6 6 6 6 6 6
0 13 13 13 13 13 13 13 3 3 3 3 3 3 3
0 10 10 10 10 10 10 10 9 9 9 9 9 9 9
0 12 12 12 12 12 12 12 5 5 5 5 5 5 5
0 4 4 4 4 4 4 4 11 11 11 11 11 11 11
0 14 14 14 14 14 14 14 7 7 7 7 7 7 7
0 2 2 2 2 2 2 2 1 1 1 1 1 1 1
0 8 8 8 8 8 8 8 10 10 10 10 10 10 10
0 12 12 12 12 12 1...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

15
0
1
2
1
1
1
2
0
2
0
2
2
1
2
0
0
2
2
0
0
0
0
2
1
1
0
2
2
0
2
0
2

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 239ms
memory: 3844kb

input:

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

output:

0 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 3...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 242ms
memory: 3832kb

input:

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

output:

0 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 91...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 275ms
memory: 3828kb

input:

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

output:

0 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 283 28...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 252ms
memory: 3852kb

input:

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

output:

0 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 662 66...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 255ms
memory: 3856kb

input:

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

output:

0 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 929 92...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 259ms
memory: 3868kb

input:

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

output:

0 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 765 76...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 259ms
memory: 3824kb

input:

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

output:

0 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 8...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 249ms
memory: 3856kb

input:

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

output:

0 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 53...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 256ms
memory: 3832kb

input:

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

output:

0 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 15...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 270ms
memory: 4160kb

input:

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

output:

0 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 593 59...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 251ms
memory: 4148kb

input:

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

output:

0 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 184 18...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 249ms
memory: 3864kb

input:

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

output:

0 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 12...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 260ms
memory: 3876kb

input:

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

output:

0 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 47...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 273ms
memory: 3828kb

input:

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

output:

0 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 928 92...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 262ms
memory: 3932kb

input:

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

output:

0 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 7...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 268ms
memory: 3856kb

input:

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

output:

0 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 565 56...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 257ms
memory: 3916kb

input:

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

output:

0 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 803 80...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 266ms
memory: 4004kb

input:

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

output:

0 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 56...

result:

ok Accepted

Test #35:

score: 0
Accepted
time: 281ms
memory: 3856kb

input:

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

output:

0 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 406 40...

result:

ok Accepted

Test #36:

score: 0
Accepted
time: 280ms
memory: 3864kb

input:

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

output:

0 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 806 80...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 247ms
memory: 3864kb

input:

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

output:

0 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 790 79...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 259ms
memory: 4156kb

input:

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

output:

0 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 55...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 271ms
memory: 3896kb

input:

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

output:

0 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 24...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 263ms
memory: 3864kb

input:

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

output:

0 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 922 92...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 272ms
memory: 3868kb

input:

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

output:

0 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 4...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed