QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#757688#8819. CNOI KnowledgeUESTC_undefined (Yicong Li, Shuaikang Peng, Yike Chen)#AC ✓137ms25080kbC++201.4kb2024-11-17 12:15:062024-11-17 12:15:07

Judging History

This is the latest submission verdict.

  • [2024-11-17 12:15:07]
  • Judged
  • Verdict: AC
  • Time: 137ms
  • Memory: 25080kb
Show
  • [2024-11-17 12:15:06]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int mod = 998244353, base = 19260817;
int n;
int ans[N + 5];
int c[N + 5];
unordered_map<int, int> lst[N + 5];
int query(int l, int r)
{
    printf("? %d %d\n", l, r);
    fflush(stdout);
    int c;
    scanf("%d", &c);
    return c;
}
void update(int p)
{
    static int d[N + 5];
    memset(d, 0, sizeof d);
    int val = 0;
    for (int i = p; i; i--)
    {
        d[i]++;
        val = (1ll * val * base + ans[i]) % mod;
        d[lst[p - i + 1][val]]--;
        lst[p - i + 1][val] = i;
    }
    for (int i = p; i; i--)
    {
        d[i] += d[i + 1];
        c[i] += d[i];
    }
}
int main()
{
    scanf("%d", &n);
    ans[1] = 1;
    c[1] = 1;
    lst[1][1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (query(1, i) == c[1] + i)
        {
            ans[i] = i;
        }
        else
        {
            int l = 1, r = i - 1, mid;
            while (l <= r)
            {
                mid = l + r >> 1;
                if (query(mid, i) == c[mid] + i - mid + 1)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            ans[i] = ans[r];
        }
        update(i);
    }
    printf("!");
    for (int i = 1; i <= n; i++)
        printf(" %d", ans[i]);
    puts("");
    fflush(stdout);
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

12
3
6
10
15
21
27
15
27
20
34
14
6
9
43
52
19
9
5
2
62
25
8
5
72
25
9
19

output:

? 1 2
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 3 7
? 1 7
? 2 7
? 1 8
? 4 8
? 6 8
? 5 8
? 1 9
? 1 10
? 5 10
? 7 10
? 8 10
? 9 10
? 1 11
? 5 11
? 8 11
? 9 11
? 1 12
? 6 12
? 9 12
? 7 12
! 1 2 3 4 5 6 2 5 9 9 5 6

result:

ok Accepted. 27 queries used.

Test #2:

score: 0
Accepted
time: 116ms
memory: 24636kb

input:

1000
3
5
5
2
7
3
2
11
7
11
16
8
5
2
21
11
3
2
27
11
5
7
34
15
8
5
3
41
15
8
5
2
48
19
7
3
2
57
19
4
3
2
66
23
5
3
2
75
20
5
3
2
84
23
5
3
2
96
23
9
13
15
108
31
14
8
5
3
124
31
15
7
5
3
140
41
16
8
5
2
156
45
15
7
3
2
172
55
20
7
15
11
188
58
21
8
5
2
208
68
21
8
5
229
69
21
8
5
2
251
80
26
12
5
8
2...

output:

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

result:

ok Accepted. 9878 queries used.

Test #3:

score: 0
Accepted
time: 125ms
memory: 24692kb

input:

1000
2
2
3
3
2
7
11
8
5
2
15
7
3
2
21
11
5
7
27
11
5
2
33
15
7
3
2
40
14
4
3
2
47
17
4
3
2
54
13
4
3
2
61
15
5
3
2
71
15
51
32
23
81
23
11
5
2
94
28
12
5
8
107
36
16
8
5
2
120
38
16
7
3
2
133
45
14
4
3
2
148
44
14
7
9
163
50
20
8
5
2
179
54
19
7
3
2
199
64
19
4
3
2
219
65
17
4
3
2
240
76
24
9
17
11
...

output:

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

result:

ok Accepted. 9876 queries used.

Test #4:

score: 0
Accepted
time: 112ms
memory: 24732kb

input:

1000
3
5
5
3
8
5
2
11
8
5
16
8
5
2
21
12
5
8
26
12
5
2
33
16
7
3
2
40
16
7
11
48
21
8
5
3
58
20
7
5
3
68
27
11
5
2
80
27
11
3
2
92
33
9
3
2
104
31
5
3
2
116
36
6
4
3
2
128
31
6
4
3
2
140
35
6
4
3
2
157
35
11
17
26
175
44
17
8
5
3
193
44
19
8
5
2
211
53
19
7
3
2
229
53
19
4
3
2
249
62
24
9
19
14
269
...

output:

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

result:

ok Accepted. 9880 queries used.

Test #5:

score: 0
Accepted
time: 96ms
memory: 24920kb

input:

1000
2
2
3
3
2
7
11
8
5
3
15
8
5
2
19
11
3
2
24
9
3
2
29
11
4
3
2
34
6
4
3
2
41
13
34
27
20
52
17
8
5
2
63
24
12
5
8
75
26
11
5
3
87
32
11
5
2
99
31
11
5
8
111
36
14
8
5
3
126
36
15
7
5
3
142
44
14
7
5
3
158
41
11
7
5
3
175
52
17
8
5
2
194
55
19
8
5
213
65
21
8
5
2
232
65
21
8
5
254
76
26
12
5
2
276...

output:

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

result:

ok Accepted. 9860 queries used.

Test #6:

score: 0
Accepted
time: 120ms
memory: 24664kb

input:

1000
2
2
5
8
5
2
12
8
5
16
8
5
2
20
12
5
8
24
12
5
2
28
16
8
5
32
16
8
5
2
36
20
8
5
46
21
8
5
3
57
27
11
5
3
68
26
9
5
3
79
31
9
5
3
90
27
9
5
3
104
34
14
8
5
2
118
34
15
8
5
132
41
14
8
5
3
146
41
15
7
5
3
160
48
19
7
5
3
174
48
17
7
5
3
194
60
17
8
5
2
216
63
19
7
3
2
238
75
25
11
5
7
260
77
27
1...

output:

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

result:

ok Accepted. 9883 queries used.

Test #7:

score: 0
Accepted
time: 134ms
memory: 24820kb

input:

1000
3
5
5
2
7
3
2
12
17
8
5
2
22
11
3
2
29
11
5
7
36
15
8
5
3
43
15
8
5
2
50
19
7
3
2
61
22
41
61
50
73
29
11
5
3
85
29
11
5
3
99
37
11
5
2
113
37
13
23
29
129
46
18
8
5
3
145
45
17
7
5
3
161
53
14
7
5
3
177
51
11
7
5
3
193
58
13
7
5
3
213
57
18
38
29
234
69
21
9
6
256
69
22
9
6
278
80
27
12
6
9
30...

output:

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

result:

ok Accepted. 9811 queries used.

Test #8:

score: 0
Accepted
time: 137ms
memory: 25080kb

input:

1000
3
5
5
2
9
13
9
13
18
9
5
3
23
12
5
3
30
11
5
2
37
15
7
3
2
45
17
37
29
22
53
23
8
5
2
63
22
7
3
2
73
27
9
3
2
84
27
63
44
35
95
35
12
21
15
109
35
13
6
9
123
42
17
9
5
2
140
42
18
8
5
157
51
17
8
5
3
175
52
15
7
5
3
194
63
21
8
5
2
214
65
23
46
37
29
234
76
23
8
5
3
255
76
23
7
5
3
279
89
30
12...

output:

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

result:

ok Accepted. 9819 queries used.

Test #9:

score: 0
Accepted
time: 127ms
memory: 24888kb

input:

1000
3
6
9
5
2
13
8
5
18
8
5
2
24
13
24
18
31
13
5
2
39
18
9
13
48
18
8
5
3
57
23
7
5
3
67
23
9
17
77
30
13
5
2
89
29
12
3
2
101
35
9
3
2
113
32
5
3
2
125
37
6
4
3
2
137
33
6
4
3
2
153
43
11
24
33
171
42
15
24
33
189
51
21
9
6
207
51
22
9
5
2
226
61
21
9
17
13
245
63
23
8
5
2
268
75
29
11
3
2
292
80...

output:

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

result:

ok Accepted. 9812 queries used.

Test #10:

score: 0
Accepted
time: 126ms
memory: 24796kb

input:

1000
2
2
5
9
13
9
6
17
9
5
2
22
12
3
2
27
12
22
17
35
17
8
5
3
43
15
7
5
3
51
22
43
36
29
62
23
9
5
2
73
30
13
5
9
86
30
13
5
3
99
37
11
5
2
112
36
11
5
8
125
42
14
8
5
3
141
41
15
7
5
3
158
50
17
32
41
177
51
17
9
5
2
196
62
23
8
5
216
61
23
9
18
13
236
71
24
9
5
2
259
74
24
9
18
13
282
86
30
13
6
...

output:

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

result:

ok Accepted. 9807 queries used.

Test #11:

score: 0
Accepted
time: 112ms
memory: 24788kb

input:

1000
2
2
5
8
5
2
12
8
5
18
24
13
6
9
30
13
5
2
38
18
8
5
47
18
9
13
56
23
9
5
3
67
24
8
5
2
78
30
13
24
18
90
30
13
5
3
103
37
11
5
2
117
36
11
3
2
132
44
17
29
22
148
45
17
9
12
165
55
17
9
5
3
183
55
17
7
5
3
201
64
21
7
5
3
220
64
21
9
15
239
75
21
9
6
258
76
23
9
5
2
277
88
30
13
5
8
296
88
31
1...

output:

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

result:

ok Accepted. 9800 queries used.

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-03-06 13:55:07 | OpenSource Project