QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#598624#9432. Permutationucup-team133#AC ✓274ms3988kbC++236.6kb2024-09-28 22:40:182024-09-28 22:40:19

Judging History

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

  • [2024-09-28 22:40:19]
  • 评测
  • 测评结果:AC
  • 用时:274ms
  • 内存:3988kb
  • [2024-09-28 22:40:18]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>


using namespace std;


#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";

template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;


template<class T>
bool chmin(T &a, T b){
  if (a>b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
bool chmax(T &a, T b){
  if (a<b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
T sum(vec<T> x){
  T res=0;
  for (auto e:x){
    res += e;
  }
  return res;
}

template<class T>
void printv(vec<T> x){
  for (auto e:x){
    cout<<e<<" ";
  }
  cout<<endl;
}



template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
  os << "(" << A.first <<", " << A.second << ")";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
  os << "set{";
  for (auto a:S){
    os << a;
    auto it = S.find(a);
    it++;
    if (it!=S.end()){
      os << ", ";
    }
  }
  os << "}";
  return os;
}

template<class T0,class T1,class T2>
ostream& operator<<(ostream& os, const tuple<T0,T1,T2>& a){
  auto [x,y,z] = a;
  os << "(" << x << ", " << y << ", " << z << ")";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const map<ll,T>& A){
  os << "map{";
  for (auto e:A){
    os << e.first;
    os << ":";
    os << e.second;
    os << ", ";
  }
  os << "}";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
  os << "[";
  rep(i,A.size()){
    os << A[i];
    if (i!=A.size()-1){
      os << ", ";
    }
  }
  os << "]" ;
  return os;
}

struct RandomNumberGenerator {
    std::mt19937 mt;

    RandomNumberGenerator() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}

    uint32_t operator()(uint32_t a, uint32_t b) {
        std::uniform_int_distribution<uint32_t> dist(a, b - 1);
        return dist(mt);
    }

    uint32_t operator()(uint32_t b) { return (*this)(0, b); }

    template <typename T> void shuffle(std::vector<T>& v) {
        for (int i = 0; i < int(v.size()); i++) std::swap(v[i], v[(*this)(0, i + 1)]);
    }
};

struct RandomNumberGenerator64 {
    std::mt19937_64 mt;

    RandomNumberGenerator64() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}

    uint64_t operator()(uint64_t a, uint64_t b) {
        std::uniform_int_distribution<uint64_t> dist(a, b - 1);
        return dist(mt);
    }

    uint64_t operator()(uint64_t b) { return (*this)(0, b); }

    template <typename T> void shuffle(std::vector<T>& v) {
        for (int i = 0; i < int(v.size()); i++) std::swap(v[i], v[(*this)(0, i + 1)]);
    }
};



void solve(){
  
  int N;
  cin>>N;

  RandomNumberGenerator64 rng;

  auto query = [&](vec<int> A){
    assert (A.size() == N);
    cout << 0 << " ";
    rep(i,N){
      cout << A[i];
      if (i == N-1){
        cout << endl;
      }
      else{
        cout << " ";
      }
    }
    int res;
    cin >> res;
    return res;
  };

  auto query_split = [&](int a,int b,int l,int m,int r,int ban){
    vec<int> A(N,ban);
    for (int i = l; i < m; i++){
      A[i] = a;
    }
    for (int i = m; i < r; i++){
      A[i] = b;
    }
    return query(A);
  };

  deque<tuple<int,int,vec<int>,int>> deq;
  vec<int> res(N,-1);

  vec<int> init_valset(N);
  rep(i,N) init_valset[i] = i+1;
  deq.push_back({0,N,init_valset,-1});

  while (!deq.empty()){
    auto [l,r,val_set,ban] = deq.front(); deq.pop_front();

    if (r-l==1){
      res[l] = val_set[0];
      continue;
    }

    int m = (l+r)>>1;
    vec<vec<int>> undet;
    for (auto x:val_set){
      undet.push_back({x});
    }
    vec<int> left_val,right_val;

    while (!undet.empty()){

      int undet_n = undet.size();
      rng.shuffle(undet);
      vec<vec<int>> nxt_undet;
      for (int i = 0; i < undet_n-1; i += 2){
        int a = undet[i][0], b = undet[i+1][0];

        int check = query_split(a,b,l,m,r,ban);

        if (check == 2){
          for (auto x:undet[i]){
            left_val.push_back(x);
          }
          for (auto x:undet[i+1]){
            right_val.push_back(x);
          }
        }
        else if (check == 0){
          for (auto x:undet[i+1]){
            left_val.push_back(x);
          }
          for (auto x:undet[i]){
            right_val.push_back(x);
          }
        }
        else{
          vec<int> merged_undet;
          for (auto x:undet[i]){
            merged_undet.push_back(x);
          }
          for (auto x:undet[i+1]){
            merged_undet.push_back(x);
          }
          nxt_undet.push_back(merged_undet);
        }
      }

      if (undet_n & 1){
        if (!nxt_undet.empty()){
          int c = nxt_undet[0].size();
          int rest_left = (m-l) - int(left_val.size());
          int rest_right = (r-m) - int(right_val.size());
          if ((rest_left % c) == (int(undet.back().size()))){
            for (auto x:undet.back()){
              left_val.push_back(x);
            }
          }
          else{
            for (auto x:undet.back()){
              right_val.push_back(x);
            }
          }
        }
        else{
          if (int(left_val.size()) != m-l){
            for (auto x:undet.back()){
              left_val.push_back(x);
            }
          }
          else{
            for (auto x:undet.back()){
              right_val.push_back(x);
            }
          }
        }
      }

      undet = nxt_undet;
    }

    deq.push_back({l,m,left_val,left_val[0]});
    deq.push_back({m,r,right_val,right_val[0]});
  }

  cout << 1 << " ";
  rep(i,N){
    cout << res[i];
    if (i == N-1){
      cout << endl;
    }
    else{
      cout << " ";
    }
  }

  return ;
  

  
  




}


int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int T = 1;
  while (T--){
    solve();
  }
}

詳細信息

Test #1:

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

input:

5
2
0
2
2
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 23...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
0
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
0
0
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
1
0
1
0
0
0
2
2

output:

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

result:

ok Accepted

Test #8:

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

input:

7
1
0
0
2
0
0
0
0
0

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 246ms
memory: 3816kb

input:

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

output:

0 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 573 57...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 253ms
memory: 3740kb

input:

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

output:

0 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 815 81...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 78...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 889 88...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 82...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 246ms
memory: 3780kb

input:

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

output:

0 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 293 29...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 37...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 883 88...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 49...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 243ms
memory: 3748kb

input:

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

output:

0 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 937 93...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 69...

result:

ok Accepted

Test #28:

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

input:

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

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 #29:

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

input:

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

output:

0 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 810 81...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 42...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 245ms
memory: 3752kb

input:

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

output:

0 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 22...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 245ms
memory: 3688kb

input:

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

output:

0 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 315 31...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 264ms
memory: 3692kb

input:

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

output:

0 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 412 41...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 240ms
memory: 3748kb

input:

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

output:

0 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 614 61...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 12...

result:

ok Accepted

Test #36:

score: 0
Accepted
time: 237ms
memory: 3688kb

input:

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

output:

0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 ...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 9...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 261ms
memory: 3808kb

input:

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

output:

0 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 597 59...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 274ms
memory: 3696kb

input:

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

output:

0 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 749 74...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 563 56...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 250ms
memory: 3908kb

input:

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

output:

0 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 420 42...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed