QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801506#9783. Duloc NetworkMrPavlitoWA 5ms3872kbC++172.1kb2024-12-07 00:52:492024-12-07 00:52:50

Judging History

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

  • [2024-12-07 00:52:50]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3872kb
  • [2024-12-07 00:52:49]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
//#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;

int query(string s)
{
    cout << "? " << s << endl;
    cout.flush();
    int x;
    cin >> x;
    return x;
}

string craft(set<int>& niz)
{
    string s;
    for(int i=0; i<n; i++)s+='0';
    for(auto x: niz)s[x] = '1';
    return s;
}

void guess(bool t)
{
    if(t)cout << "! 1" << endl;
    else cout << "! 0" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n;
        vector<int> cnt(n+1);
        string s;
        for(int i=0; i<n; i++)s+='0';
        set<int> org;
        for(int i=0; i<n; i++)
        {
            s[i] = '1';
            cnt[i] = query(s);
            s[i] = '0';
        }
        org.insert(0);
        bool resenje = 1;
        for(int i = 1; i<n; i++)
        {
            int trenutno = query(craft(org));
            int l = i;
            int r = n-1;
            int rez = n;
            while(l<=r)
            {
                int mid = l+r >> 1;
                set<int> niz = org;
                for(int j= i; j<=mid; j++)niz.insert(j);
                set<int> setic;
                for(auto x:niz)if(!org.count(x))setic.insert(x);
                int trcnt = 0;
                int tre1 = query(craft(niz));
                int tre2 = query(craft(setic));
                if(trenutno + tre2 == tre1)l = mid+1;
                else
                {
                    r = mid-1;
                    rez = mid;
                }
            }
            if(rez == n)
            {
                resenje = false;
                break;
            }
            org.insert(rez);
            //for(auto x: org)cout << x << " ";cout << endl;
        }
        guess(resenje);

    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

? 1000
? 0100
? 0010
? 0001
? 1000
? 1110
? 0110
? 1100
? 0100
? 1100
? 1110
? 0010
? 1110
? 1111
? 0001
! 1

result:

ok Correct answer with 15 queries.

Test #2:

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

input:

2
0
0
0
0
0

output:

? 10
? 01
? 10
? 11
? 01
! 0

result:

ok Correct answer with 5 queries.

Test #3:

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

input:

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

output:

? 1000
? 0100
? 0010
? 0001
? 1000
? 1110
? 0110
? 1100
? 0100
? 1100
? 1110
? 0010
? 1110
? 1111
? 0001
! 1

result:

ok Correct answer with 15 queries.

Test #4:

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

input:

2
0
0
0
0
0

output:

? 10
? 01
? 10
? 11
? 01
! 0

result:

ok Correct answer with 5 queries.

Test #5:

score: 0
Accepted
time: 3ms
memory: 3652kb

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

output:

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

result:

ok Correct answer with 455 queries.

Test #6:

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

input:

50
10
13
8
6
13
8
10
8
8
8
9
13
15
11
9
10
14
6
16
10
15
10
7
8
10
10
10
13
10
15
9
10
11
5
16
10
14
11
10
9
9
15
11
10
7
11
12
10
9
10
10
24
25
36
36
33
32
22
20
19
13
19
24
26
35
37
34
31
30
23
21
8
21
23
26
34
37
35
32
32
22
22
6
22
23
27
34
37
35
29
32
18
30
13
30
22
27
33
37
35
26
33
16
32
8
32...

output:

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

result:

ok Correct answer with 485 queries.

Test #7:

score: 0
Accepted
time: 3ms
memory: 3612kb

input:

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

output:

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

result:

ok Correct answer with 407 queries.

Test #8:

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

input:

50
2
14
8
8
7
12
12
8
8
9
9
10
8
8
4
8
9
9
9
11
13
11
8
7
9
12
7
5
6
4
7
8
10
5
5
10
8
4
10
9
11
7
10
8
6
8
10
7
5
9
2
24
23
31
30
33
32
24
23
15
14
15
24
24
30
29
33
30
27
21
21
8
21
23
25
31
31
33
29
30
23
24
8
24
23
26
31
32
33
28
30
18
27
7
27
22
27
31
34
33
29
33
22
30
12
30
22
28
31
35
32
28
3...

output:

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

result:

ok Correct answer with 485 queries.

Test #9:

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

input:

50
3
1
1
1
2
1
1
1
1
5
1
2
1
1
1
1
3
1
1
2
1
1
1
2
2
1
1
1
1
3
1
2
1
1
2
3
1
2
3
2
1
3
1
2
3
1
2
2
1
1
3
15
16
13
13
6
6
4
3
4
1
5
2
2
15
16
13
13
6
6
3
3
3
1
3
1
2
14
16
13
11
13
13
14
12
13
13
1
14
15
12
11
13
12
14
13
15
14
15
14
0
14
14
9
9
5
5
4
4
3
3
2
2

output:

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

result:

ok Correct answer with 113 queries.

Test #10:

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

input:

100
1
2
1
1
1
1
1
1
3
3
1
1
2
3
4
1
2
2
2
1
2
2
1
2
2
1
1
1
3
2
1
2
2
1
4
1
1
1
3
2
4
1
3
2
3
3
3
1
1
1
1
2
1
2
2
4
3
1
2
1
1
1
1
3
3
3
2
1
1
2
1
2
2
3
2
1
5
3
5
1
1
1
1
1
1
1
1
3
4
1
2
1
2
1
1
2
1
3
2
1
1
29
28
21
22
27
28
28
27
27
26
26
27
0
28
28
21
21
11
11
7
7
4
4
2
2
1
1

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 128 queries.

Test #11:

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

input:

100
11
13
9
11
8
7
15
12
8
8
7
6
9
12
11
9
10
9
11
16
10
8
9
8
10
6
8
9
13
10
9
7
5
11
14
6
11
16
7
7
8
8
11
8
13
15
11
12
11
11
11
9
10
12
10
6
11
10
5
13
9
9
6
6
6
12
7
12
10
10
9
11
7
11
5
6
9
6
5
9
5
16
11
13
13
10
5
5
8
8
12
11
5
8
8
10
8
10
8
10
11
48
49
64
65
61
60
48
46
33
27
23
13
23
48
50
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1159 queries.

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3644kb

input:

100
5
3
3
4
2
2
2
8
4
5
4
4
2
2
3
4
6
5
1
4
3
3
2
5
5
2
2
4
3
4
4
4
4
1
3
5
3
4
4
3
3
4
1
3
3
2
5
5
5
1
3
4
3
4
2
2
4
2
1
3
3
7
3
5
5
6
6
1
3
2
3
3
3
2
1
6
3
5
5
3
4
4
2
2
1
5
7
3
3
1
6
2
2
5
2
5
3
3
6
4
5
36
36
46
46
32
29
19
16
14
10
8
3
11
6
8
37
38
46
44
32
27
21
15
13
5
15
7
16
9
9
39
39
46
42
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer Wrong answer.