QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488888 | #8819. CNOI Knowledge | dalao_see_me | TL | 1ms | 3860kb | C++14 | 1.4kb | 2024-07-24 16:06:09 | 2024-07-24 16:06:11 |
Judging History
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 ...