QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#814541#9783. Duloc Networkucup-team4967#WA 1ms3780kbC++202.3kb2024-12-14 18:08:582024-12-14 18:08:58

Judging History

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

  • [2024-12-14 18:08:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3780kb
  • [2024-12-14 18:08:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 2305843009213693951
#define REP(i,n) for(ll i=0;i<(n);i++)

ll N;
ll remQ = 3500;

void input(void){
    cin >> N;
}

void output(int c){
    cout << "! " << c << endl;
    exit(0);
}

map<vector<ll>,ll> memo;

ll query(vector<ll> C){

    if((ll)C.size() == N){
        return 0;
    }

    if(memo.find(C)!=memo.end()){
        return memo[C];
    }

    assert(remQ > 0);

    string S(N,'0');
    for(ll c:C){
        S[c] = '1';
    }
    cout << "? " << S << endl;
    remQ--;
    ll c;
    cin >> c;

    memo[C] = c;
    return c;
}



int main(void){
    
    input();

    vector<pair<vector<ll>,ll>> C(N);
    REP(i,N){
        C[i] = {{i},query({i})};
    }

    // C の [l,r) に連結なところはあるか
    function<ll(ll,ll)> ask = [&](ll l, ll r){
        assert(0<=l && l<r && r<=(ll)C.size());

        vector<ll> E;
        ll sum = 0;
        for(ll x=l;x<r;x++){
            for(ll e:C[x].first){
                E.push_back(e);
            }
            sum += C[x].second;
        }
        ll q = query(E);
        if(q < sum){ // 連結あり
            return 1;
        }

        // 孤立
        return 0;

    };

    while(1){

        // cerr << "$$$ " << endl;
        // REP(i,(ll)C.size()){
        //     REP(j,(ll)C[i].first.size()){
        //         cerr << C[i].first[j] << " ";
        //     }
        //     cerr << "  " << C[i].second << endl;
        // }cerr << endl;

        if(C.size()==1){
            output(1);
        }

        ll l = 0, r = C.size();
        if(ask(l,r)==0){
            output(0);
        }

        while(abs(r-l)>2){

            ll m = (l+r)/2;
            if(ask(l,m)==1){
                r = m;
            }else{
                l = m;
            }

        }

        // l と l+1 が連結
        pair<vector<ll>,ll> s;
        s.first = C[l].first;
        for(ll e:C[l+1].first){
            s.first.push_back(e);
        }
        s.second = ask(l,l+1);
        for(ll x=l;x+2<(ll)C.size();x++){
            C[x] = C[x+2];
        }
        C.pop_back();
        C.pop_back();
        C.push_back(s);

    }

    return 0;
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1
3
2
2
2

output:

? 1000
? 0100
? 0010
? 0001
? 1100
! 1

result:

ok Correct answer with 5 queries.

Test #2:

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

input:

2
0
0

output:

? 10
? 01
! 0

result:

ok Correct answer with 2 queries.

Test #3:

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

input:

4
1
3
2
2
2

output:

? 1000
? 0100
? 0010
? 0001
? 1100
! 1

result:

ok Correct answer with 5 queries.

Test #4:

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

input:

2
0
0

output:

? 10
? 01
! 0

result:

ok Correct answer with 2 queries.

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3780kb

input:

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

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

wrong answer Wrong answer.