QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#801530#9783. Duloc NetworkMrPavlitoWA 6ms4008kbC++172.6kb2024-12-07 01:12:122024-12-07 01:12:13

Judging History

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

  • [2024-12-07 01:12:13]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：4008kb
查看
  • [2024-12-07 01:12:12]
  • 提交

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;
}

map<string,int> mapa;

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;
        org.insert(0);
        bool resenje = 1;
        for(int i = 1; i<n; i++)
        {
            int trenutno = 0;
            string trs = craft(org);
            if(mapa.count(trs))trenutno = mapa[trs];
            else
            {
                trenutno = query(trs);
                mapa[trs] = trenutno;
            }
            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);
                trs = craft(niz);
                int tre1 = 0;
                if(mapa.count(trs))tre1 = mapa[trs];
                else
                {
                    tre1 = query(trs);
                    mapa[trs] = tre1;
                }
                trs = craft(setic);
                int tre2 = 0;
                if(mapa.count(trs))tre2 = mapa[trs];
                else
                {
                    tre2 = query(trs);
                    mapa[trs] = tre2;
                }
                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);

    }
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

4
1
1
2
2
3
2
0
2

output:

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

result:

ok Correct answer with 8 queries.

Test #2:

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

input:

2
0
0
0

output:

? 10
? 11
? 01
! 0

result:

ok Correct answer with 3 queries.

Test #3:

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

input:

4
1
1
2
2
3
2
0
2

output:

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

result:

ok Correct answer with 8 queries.

Test #4:

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

input:

2
0
0
0

output:

? 10
? 11
? 01
! 0

result:

ok Correct answer with 3 queries.

Test #5:

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

input:

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

output:

? 10000000000000000000000000000000000000000000000000
? 11111111111111111111111111000000000000000000000000
? 01111111111111111111111111000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 01111111111110000000000000000000000000000000000000
? 111111100000000000000000000000000...

result:

ok Correct answer with 259 queries.

Test #6:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

50
10
24
25
36
36
33
32
22
20
19
13
26
35
37
34
31
30
23
21
8
23
26
34
37
35
32
32
22
6
27
37
29
18
13
22
27
33
37
35
26
16
8
28
32
37
34
30
15
10
21
28
31
36
35
33
16
8
29
37
34
13
8
20
29
31
38
35
17
8
30
30
37
36
21
9
19
30
29
39
34
23
13
31
40
31
22
15
18
31
28
39
32
20
11
32
27
40
30
17
9
17
32...

output:

? 10000000000000000000000000000000000000000000000000
? 11111111111111111111111111000000000000000000000000
? 01111111111111111111111111000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 01111111111110000000000000000000000000000000000000
? 111111100000000000000000000000000...

result:

ok Correct answer with 243 queries.

Test #7:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

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

output:

? 10000000000000000000000000000000000000000000000000
? 11111111111111111111111111000000000000000000000000
? 01111111111111111111111111000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 01111111111110000000000000000000000000000000000000
? 111111111111111111100000000000000...

result:

ok Correct answer with 258 queries.

Test #8:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

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

output:

? 10000000000000000000000000000000000000000000000000
? 11111111111111111111111111000000000000000000000000
? 01111111111111111111111111000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 01111111111110000000000000000000000000000000000000
? 111111100000000000000000000000000...

result:

ok Correct answer with 243 queries.

Test #9:

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

input:

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

output:

? 10000000000000000000000000000000000000000000000000
? 11111111111111111111111111000000000000000000000000
? 01111111111111111111111111000000000000000000000000
? 11111111111110000000000000000000000000000000000000
? 01111111111110000000000000000000000000000000000000
? 111111100000000000000000000000000...

result:

ok Correct answer with 58 queries.

Test #10:

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

input:

100
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
? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000
? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...

result:

ok Correct answer with 28 queries.

Test #11:

score: 0
Accepted
time: 6ms
memory: 4008kb

input:

100
11
48
49
64
65
61
60
48
46
33
27
23
13
50
65
63
60
50
46
40
26
27
9
47
50
64
66
64
62
53
48
43
25
11
51
65
68
63
57
55
43
26
8
46
51
65
68
62
58
57
41
30
7
52
69
56
37
25
15
45
52
66
70
64
54
58
32
20
12
53
65
68
66
54
33
16
8
44
53
64
68
67
55
35
15
8
52
66
67
54
35
13
7
43
53
63
66
67
55
35
15...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000
? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...

result:

ok Correct answer with 580 queries.

Test #12:

score: -100
Wrong Answer
time: 4ms
memory: 4000kb

input:

100
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
33
26
22
14
13
4
18
10
16
40
46
41
36
25
25
11
16
2
38
39
46
40
37
25
26
12
2
6
9
18
39
41
47
40
38
23
26
9
0
21
4
38
41
46
39
39
23
29
8
33
13
30
9
31
11
22
42
45
38
40
22
36
15
11
25
38
43
44
38
40
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000
? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...

result:

wrong answer Wrong answer.
English 繁體中文 简体中文

伺服器時間: 2025-01-20 17:08:45 | 開源專案