QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488831 | #8819. CNOI Knowledge | dalao_see_me | WA | 1ms | 3840kb | C++14 | 1.2kb | 2024-07-24 15:38:11 | 2024-07-24 15:38: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];
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;
for (int i = 1; i <= n; i++) {
int L = 0, R = i - 1;
while (L < R) {
int mid = L + R + 1 >> 1;
if (ask(mid, i) - ask(mid, i - 1) == i - mid + 1) L = mid;
else R = mid - 1;
}
if (L) b[i] = b[L];
else b[i] = ++tot;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
input:
12 3 1 6 3 1 6 3 1 10 6 3 1 10 6 3 1 15 6 3 1 14 10 26 20 34 27 20 10 6 6 3 3 1 19 14 42 34 52 43 25 51 62 25 19 50 42 72
output:
? 1 2 ? 1 1 ? 1 3 ? 2 3 ? 2 2 ? 2 4 ? 3 4 ? 3 3 ? 2 5 ? 3 5 ? 4 5 ? 4 4 ? 3 6 ? 4 6 ? 5 6 ? 5 5 ? 3 7 ? 5 7 ? 6 7 ? 6 6 ? 4 8 ? 4 7 ? 2 8 ? 2 7 ? 1 8 ? 1 7 ? 4 9 ? 6 9 ? 6 8 ? 7 9 ? 7 8 ? 8 9 ? 8 8 ? 5 10 ? 5 9 ? 2 10 ? 2 9 ? 1 10 ? 1 9 ? 5 11 ? 2 11 ? 1 11 ? 6 12 ? 6 11 ? 3 12 ? 3 11 ? 1 12 1 1 1 1...
result:
wrong answer Invalid output.