QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488888#8819. CNOI Knowledgedalao_see_meTL 1ms3860kbC++141.4kb2024-07-24 16:06:092024-07-24 16:06:11

Judging History

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

  • [2024-07-24 16:06:11]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3860kb
  • [2024-07-24 16:06:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
    return x * f;
}
const int N = 1005;
int n;
int a[N][N], b[N], c[N];
int ask(int l, int r) {
    if (~a[l][r]) return a[l][r];
    printf("? %d %d\n", l, r); fflush(stdout);
    return a[l][r] = read();
}
void Solve() {
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = -1;
    for (int i = 1; i <= n; i++) a[i][i - 1] = 0;
    int tot = 0;
    c[1] = 1;
    for (int i = 2; c[i - 1] <= n; i++) c[i] = c[i - 1] * 2;
    for (int i = 1, j = 0, k; i <= n; i++) {
        while (c[j + 1] < i) j++; k = j;
        while (k && ask(c[k], i) - ask(c[k], i - 1) == i - c[k] + 1) k--;
        if (!k) {b[i] = ++tot; continue;}
        int L = c[k], R = min(i, c[k + 1]) - 1;
        while (L < R) {
            int mid = L + R + 1 >> 1;
            if (ask(mid, i) - ask(mid, i - 1) <= i - mid) L = mid;
            else R = mid - 1;
        }
        b[i] = b[L];
    }
    putchar('!');
    for (int i = 1; i <= n; i++) printf(" %d", b[i]); putchar('\n');
}
int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int _ = 1;
    while (_--) Solve();
    return 0;
}

詳細信息

Test #1:

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

input:

12
3
1
3
1
6
6
10
3
1
10
15
6
15
21
10
20
15
10
14
6
3
9
6
3
1
20
34
26
43
34
5
2
1
8
5
13
40
33
25
19
19
13

output:

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

result:

ok Accepted. 42 queries used.

Test #2:

score: -100
Time Limit Exceeded

input:

1000
3
1
2
1
3
2
1
3
1
7
11
7
5
2
1
7
3
2
1
11
5
7
3
1
15
8
5
3
5
2
1
7
3
2
1
9
3
2
1
11
4
3
2
1
13
4
3
2
1
15
5
3
2
1
23
9
4
13
6
15
7
3
1
31
14
8
5
5
3
5
3
1
8
5
2
1
11
3
2
1
15
7
11
7
21
8
5
5
3
2
1
27
12
5
8
33
12
5
3
2
1
40
16
8
5
47
16
12
8
5
3
2
1
54
20
8
5
65
21
16
8
5
3
3
1
76
26
11
5
2
1
8...

output:

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

result: