QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786863#9783. Duloc Networkucup-team1134WA 70ms8140kbC++2313.8kb2024-11-27 00:16:062024-11-27 00:16:06

Judging History

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

  • [2024-11-27 00:16:06]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:8140kb
  • [2024-11-27 00:16:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

// BIT セグ木 遅延セグ木 のみ

// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)

#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;

template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
                           std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <vector>

namespace atcoder {

template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;
    
public:
    fenwick_tree() : _n(0) {}
    fenwick_tree(int n) : _n(n), data(n) {}
    
    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }
    
    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }
    
private:
    int _n;
    std::vector<U> data;
    
    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder


#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
namespace atcoder {

template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }
        
        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        
        return op(sml, smr);
    }
    
    S all_prod() { return d[1]; }
    
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    
    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    
    S all_prod() { return d[1]; }
    
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
private:
    int _n, size, log;
    std::vector<S> d;
    
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using T=set<int>;

T f(T a,T b){
    T res;
    for(int x:a) res.insert(x);
    for(int x:b) res.insert(x);
    return res;
}

T ti(){
    return {};
}

int N;

map<set<int>,int> MA;

int ask(set<int> X){
    if(MA.count(X)) return MA[X];
    else{
        cout<<"? ";
        for(int i=0;i<N;i++){
            if(X.count(i)) cout<<'1';
            else cout<<'0';
        }
        cout<<endl;
        int z;cin>>z;
        return MA[X]=z;
    }
}

int main(){
    
    cin>>N;
    vector<T> def(N);
    for(int i=0;i<N;i++){
        def[i].insert(i);
    }
    
    atcoder::segtree<T,f,ti> seg(def);
    
    for(int s=N-1;s>=1;s--){
        auto check=[&](int a,int b){
            auto A=seg.prod(a,b);
            set<int> B={s},C=A;
            C.insert(s);
            int aa=ask(A),bb=ask(B),cc=ask(C);
            if(aa+bb>cc) return true;
            else return false;
        };
        int l=0,r=s;
        if(!check(l,r)){
            cout<<"! 0"<<endl;
            return 0;
        }
        while(r-l>1){
            int m=(l+r)/2;
            if(check(l,m)){
                r=m;
            }else{
                l=m;
            }
        }
        auto A=seg.get(l);A.insert(s);
        seg.set(l,A);
    }
    
    cout<<"! 1"<<endl;
    
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1
2
0
1
2
1
2
1
3

output:

? 1110
? 0001
? 1111
? 1000
? 1001
? 1101
? 0010
? 1011
? 0100
! 1

result:

ok Correct answer with 9 queries.

Test #2:

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

input:

2
0
0
0

output:

? 10
? 01
? 11
! 0

result:

ok Correct answer with 3 queries.

Test #3:

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

input:

4
1
2
0
1
2
1
2
1
3

output:

? 1110
? 0001
? 1111
? 1000
? 1001
? 1101
? 0010
? 1011
? 0100
! 1

result:

ok Correct answer with 9 queries.

Test #4:

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

input:

2
0
0
0

output:

? 10
? 01
? 11
! 0

result:

ok Correct answer with 3 queries.

Test #5:

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

input:

50
1
3
0
15
16
16
17
10
12
5
7
3
5
1
2
15
17
14
5
7
2
3
1
3
16
18
15
17
9
11
6
9
1
4
1
3
1
1
19
19
19
10
11
6
6
2
2
1
2
17
18
18
12
7
6
1
6
17
17
13
12
11
1
3
18
17
18
18
14
15
2
1
3
19
20
16
14
13
1
3
20
19
19
15
13
12
1
1
18
19
15
14
3
4
1
1
18
17
17
18
9
8
3
4
3
2
1
4
16
17
14
15
17
4
1
2
16
15
1...

output:

? 11111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111
? 11111111111111111111111100000000000000000000000000
? 11111111111111111111111100000000000000000000000001
? 111111111111000000000000000000000...

result:

ok Correct answer with 156 queries.

Test #6:

score: 0
Accepted
time: 7ms
memory: 4300kb

input:

50
1
10
0
26
25
35
35
32
34
21
26
10
17
1
9
24
35
36
31
25
1
10
25
24
35
35
36
36
29
32
28
1
12
23
34
36
34
31
1
11
24
23
33
37
36
34
1
7
22
32
37
37
35
1
10
23
22
33
32
36
38
36
1
11
21
31
35
37
35
1
15
22
21
31
36
38
37
1
9
20
30
35
37
36
1
9
21
20
31
30
35
34
36
36
1
10
19
29
33
35
35
1
11
20
19
...

output:

? 11111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111
? 11111111111111111111111100000000000000000000000000
? 11111111111111111111111100000000000000000000000001
? 111111111111000000000000000000000...

result:

ok Correct answer with 328 queries.

Test #7:

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

input:

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

output:

? 11111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111
? 11111111111111111111111100000000000000000000000000
? 11111111111111111111111100000000000000000000000001
? 111111111111000000000000000000000...

result:

ok Correct answer with 244 queries.

Test #8:

score: 0
Accepted
time: 7ms
memory: 4080kb

input:

50
1
9
0
26
25
32
33
30
32
21
25
2
11
14
19
1
5
24
32
32
27
7
21
1
7
25
24
33
33
32
35
22
27
9
1
10
23
32
35
30
11
1
8
24
23
33
36
32
16
1
6
22
32
36
33
19
1
8
23
22
33
32
35
33
21
1
10
21
31
35
33
24
1
7
22
21
31
35
33
27
1
11
20
30
35
34
30
1
9
21
20
31
30
36
35
33
30
1
10
19
29
34
32
29
1
4
20
19...

output:

? 11111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111
? 11111111111111111111111100000000000000000000000000
? 11111111111111111111111100000000000000000000000001
? 111111111111000000000000000000000...

result:

ok Correct answer with 331 queries.

Test #9:

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

input:

50
1
1
0
14
15
14
15
9
10
6
7
3
2
1
0
1
1
15
14
9
9
4
4
2
2
1
2
15
14
10
10
4
6
3
4
1
3
1
3
1
2
13
11
6
6
1
2
0

output:

? 11111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111
? 11111111111111111111111100000000000000000000000000
? 11111111111111111111111100000000000000000000000001
? 000000000000000000000000111111111...

result:

ok Correct answer with 48 queries.

Test #10:

score: 0
Accepted
time: 4ms
memory: 4172kb

input:

100
1
1
0
31
31
25
25
15
15
7
8
5
6
3
4
1
2
1
2
30
25
17
11
13
5
6
2
4
1
3
1
3
29
29
27
18
14
8
4
1
1
29
28
19
19
9
10
5
5
1
1
1
2
30
32
23
22
14
14
7
9
6
6
2
4
2
3
1
1
29
28
29
20
21
9
8
3
4
3
4
2
1
1
1
30
31
26
25
17
18
7
8
9
8
3
4
3
4
1
2
32
25
19
7
4
6
1
3
1
1
1
1
30
29
27
28
16
17
11
10
6
5
1
2...

output:

? 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct answer with 445 queries.

Test #11:

score: 0
Accepted
time: 20ms
memory: 5568kb

input:

100
1
10
0
50
49
65
64
58
61
43
48
27
35
11
20
1
8
48
64
62
49
37
25
1
10
49
48
63
63
53
41
32
1
8
47
65
65
56
47
39
1
10
48
47
66
66
64
64
54
56
46
51
44
1
8
46
66
66
58
54
48
1
8
47
46
65
66
58
54
48
1
5
45
64
65
60
57
51
1
11
46
45
65
65
68
63
60
54
1
12
44
64
67
63
61
55
1
8
45
45
64
68
64
62
56...

output:

? 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct answer with 762 queries.

Test #12:

score: 0
Accepted
time: 20ms
memory: 5532kb

input:

100
1
4
0
37
38
46
48
31
34
18
21
11
15
4
7
1
6
39
50
37
25
16
5
10
1
3
38
37
49
36
25
18
13
3
5
1
3
36
49
39
18
19
7
10
4
5
1
5
37
37
48
49
35
40
18
19
8
12
4
9
2
6
1
2
37
49
37
20
13
6
7
1
5
37
37
50
40
23
16
9
10
1
2
38
51
36
23
24
15
16
11
1
2
39
40
50
51
37
26
12
14
4
5
1
6
39
51
38
28
20
15
1
...

output:

? 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct answer with 780 queries.

Test #13:

score: 0
Accepted
time: 12ms
memory: 4204kb

input:

100
1
1
0
33
32
39
38
20
19
8
7
3
4
3
2
1
2
31
37
18
7
5
2
1
1
32
32
37
19
13
13
6
6
4
4
1
1
32
37
18
7
3
1
2
1
1
1
1
33
34
29
28
21
20
13
12
8
9
1
2
2
3
1
3
33
35
36
15
18
15
17
8
11
1
4
2
4
1
1
33
32
35
16
18
6
5
1
0
1
4
31
35
16
6
7
2
3
5
1
5
31
31
34
37
21
13
16
7
10
3
6
1
1
30
36
15
8
5
6
4
5
1...

output:

? 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct answer with 458 queries.

Test #14:

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

input:

100
1
1
0
32
31
26
26
15
16
10
10
6
7
1
2
1
2
1
2
31
28
16
18
7
9
7
7
2
4
3
5
1
1
30
31
26
27
17
18
14
13
7
8
2
1
1
2
30
28
18
9
7
4
5
1
1
29
29
26
26
14
14
8
8
2
3
2
3
3
4
1
1
29
26
14
9
6
6
3
4
2
2
1
3
30
30
28
16
11
8
6
4
1
2
32
26
26
14
14
5
5
2
4
1
1
1
1
30
29
27
26
15
7
3
1
1
3
30
29
12
13
6
7...

output:

? 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct answer with 458 queries.

Test #15:

score: 0
Accepted
time: 59ms
memory: 8140kb

input:

150
1
2
0
60
60
57
58
42
43
24
26
11
13
10
12
1
3
3
5
1
4
59
59
45
27
11
15
5
8
2
6
1
3
59
58
58
58
45
29
14
10
5
1
6
58
59
49
33
16
6
11
4
10
1
3
56
55
59
49
36
12
7
10
2
3
1
4
54
58
49
34
19
14
7
1
4
55
56
57
58
48
51
33
37
13
16
6
10
4
7
1
3
56
58
53
36
18
9
9
1
2
55
54
58
53
35
20
6
8
6
8
3
1
2
...

output:

? 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1305 queries.

Test #16:

score: 0
Accepted
time: 45ms
memory: 7848kb

input:

150
1
5
0
54
54
52
53
35
38
21
25
9
13
6
10
4
8
1
2
54
54
39
26
15
3
5
1
3
8
9
1
3
55
54
55
55
40
29
7
8
3
4
2
5
1
2
55
56
41
27
15
5
3
10
1
3
55
54
57
42
29
16
6
4
12
1
3
54
58
44
31
15
12
10
1
4
54
54
56
58
43
45
30
34
7
11
5
9
1
5
4
6
1
3
54
58
47
32
18
5
2
5
1
3
54
53
57
46
31
18
8
4
1
1
53
57
4...

output:

? 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1304 queries.

Test #17:

score: 0
Accepted
time: 20ms
memory: 6180kb

input:

150
1
4
0
63
62
57
57
34
37
18
22
9
13
11
15
1
4
1
3
61
56
37
18
9
10
4
7
4
5
1
1
61
60
55
54
36
17
11
6
5
4
3
1
3
59
53
36
17
11
7
6
1
3
59
58
54
39
21
24
11
14
8
11
2
3
1
1
57
53
35
18
8
4
5
1
0
1
2
57
56
53
54
34
35
16
17
13
7
3
4
1
2
55
55
37
21
22
9
10
3
4
1
3
1
3
54
54
57
37
19
13
6
3
6
1
2
54...

output:

? 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1123 queries.

Test #18:

score: 0
Accepted
time: 37ms
memory: 6724kb

input:

150
1
2
0
66
66
65
65
41
41
27
29
11
11
6
6
4
6
1
1
65
65
41
27
17
17
8
9
5
5
1
4
64
64
64
67
44
30
20
12
8
1
2
64
69
36
36
20
22
12
12
5
7
2
4
1
2
64
63
68
45
32
12
7
5
1
3
62
68
45
32
23
4
7
5
7
1
2
63
62
65
64
42
41
31
31
20
10
8
1
4
61
65
44
34
23
12
11
1
3
62
62
65
45
35
24
11
12
1
1
61
64
44
3...

output:

? 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1086 queries.

Test #19:

score: 0
Accepted
time: 20ms
memory: 4708kb

input:

150
1
3
0
50
50
42
45
30
31
16
17
7
10
5
6
2
5
1
1
50
42
22
23
20
20
8
9
3
4
2
3
5
6
1
1
48
47
41
40
23
19
9
4
3
6
1
4
47
41
26
20
12
7
6
9
1
1
48
49
37
36
28
29
17
18
5
6
4
3
2
3
1
1
47
40
22
13
13
7
8
4
5
2
2
1
1
47
47
39
39
20
20
14
14
7
3
4
1
2
1
1
46
40
27
28
21
22
8
7
4
3
2
3
1
3
46
45
39
23
1...

output:

? 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 624 queries.

Test #20:

score: 0
Accepted
time: 27ms
memory: 5288kb

input:

200
1
1
0
64
64
49
49
32
32
17
17
10
11
3
3
1
2
1
1
1
1
64
50
30
31
16
17
11
11
7
8
2
2
1
1
64
63
48
32
17
11
4
1
1
1
2
63
48
34
16
16
9
11
4
6
1
3
1
1
1
1
62
61
49
48
33
15
10
5
2
0
1
1
60
47
31
18
12
11
7
6
3
2
1
3
59
58
47
32
18
11
5
6
1
2
1
1
59
55
54
28
27
14
13
7
6
4
3
2
1
1
1
59
58
48
48
31
3...

output:

? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 812 queries.

Test #21:

score: 0
Accepted
time: 70ms
memory: 7896kb

input:

200
1
3
0
65
65
61
62
39
40
20
23
10
13
4
7
3
4
1
3
66
64
43
17
20
15
17
8
11
3
6
2
4
1
4
67
67
64
42
24
12
6
8
2
6
2
6
1
1
67
65
35
35
20
20
8
9
8
8
3
4
2
3
1
1
68
67
64
63
41
21
13
5
3
1
2
66
63
43
19
17
10
5
4
1
1
67
66
64
36
35
21
22
8
7
3
4
1
2
2
3
1
3
65
63
41
23
12
9
5
3
1
1
66
65
62
63
31
30...

output:

? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1702 queries.

Test #22:

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

input:

200
1
3
0
72
71
64
64
37
37
18
19
9
10
4
7
1
4
1
4
1
1
72
60
59
45
45
23
24
12
13
7
8
4
5
3
3
1
1
70
69
65
39
38
29
29
16
17
7
8
3
3
1
4
69
65
39
23
12
16
6
9
3
7
1
4
1
1
70
70
64
64
40
24
25
14
14
8
8
3
4
3
3
1
1
71
59
60
37
38
20
21
8
9
5
4
1
2
1
0
1
2
71
70
66
37
37
28
28
12
14
9
11
3
5
5
1
3
69
...

output:

? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 175 queries.

Test #23:

score: -100
Wrong Answer
time: 57ms
memory: 7348kb

input:

200
1
3
0
69
69
62
65
36
39
22
22
12
14
4
7
3
6
2
4
1
1
68
61
34
34
19
20
11
12
5
6
2
3
3
3
1
2
67
68
62
36
28
30
11
13
5
6
2
4
1
2
1
1
67
62
34
19
7
8
6
7
1
2
4
4
1
3
67
66
61
61
35
20
10
7
3
4
1
1
66
62
34
34
18
18
11
12
6
6
2
3
2
2
1
5
66
67
65
40
32
16
21
10
14
2
6
1
1
67
66
35
21
21
9
10
8
8
4
...

output:

? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer Wrong answer.