QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489479 | #8819. CNOI Knowledge | _log_ | WA | 13ms | 7596kb | C++17 | 921b | 2024-07-24 20:32:48 | 2024-07-24 20:32:49 |
Judging History
answer
# include <bits/stdc++.h>
# define maxn 1005
# define rep(i, j, k) for(int i = j; i <= k; ++i)
using namespace std;
int n, a[maxn], tot;
int ans[maxn][maxn];
int query(int l, int r) {
if(l > r) return 0;
if(ans[l][r] != -1) return ans[l][r];
cout << "? " << l << ' ' << r << endl;
cin >> ans[l][r];
return ans[l][r];
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(ans, -1, sizeof(ans));
cin >> n; a[1] = ++tot;
rep(i, 2, n) {
if(query(1, i) - query(1, i - 1) == i) {a[i] = ++tot; continue;}
int l = 1, r = i, pos;
while(l <= r) {
int mid = l + r >> 1;
if(query(mid, i) - query(mid, i - 1) == i - mid + 1) pos = mid - 1, r = mid - 1;
else l = mid + 1;
}
a[i] = a[pos];
}
cout << "! ";
rep(i, 1, n) cout << a[i] << ' ';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7596kb
input:
12 3 1 6 10 15 21 27 10 6 20 15 15 10 34 14 6 3 9 6 43 52 19 14 5 3 2 1 1 62 19 14 5 13 9 8 72 25 9 19
output:
? 1 2 ? 1 1 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 7 ? 4 6 ? 2 7 ? 2 6 ? 3 7 ? 3 6 ? 1 8 ? 4 8 ? 6 8 ? 6 7 ? 5 8 ? 5 7 ? 1 9 ? 1 10 ? 5 10 ? 5 9 ? 8 10 ? 8 9 ? 9 10 ? 9 9 ? 10 10 ? 1 11 ? 6 11 ? 6 10 ? 9 11 ? 7 11 ? 7 10 ? 8 11 ? 1 12 ? 6 12 ? 9 12 ? 7 12 ! 1 2 3 4 5 6 2 5 7 7 5 6
result:
ok Accepted. 39 queries used.
Test #2:
score: -100
Wrong Answer
time: 13ms
memory: 7504kb
input:
1000 3 1 5 2 1 1 7 3 2 1 11 5 7 16 8 2 1 1 21 7 5 2 1 27 11 5 7 3 34 11 5 3 3 1 41 15 5 2 1 1 48 15 11 3 2 1 57 19 4 2 1 66 17 14 4 3 2 1 75 20 4 3 2 1 84 15 13 4 3 2 1 96 23 9 13 6 15 7 108 23 11 7 5 3 3 1 124 31 11 8 5 3 1 140 36 27 11 7 5 2 1 1 156 45 15 3 2 1 172 48 39 15 11 5 11 7 7 188 58 16 5...
output:
? 1 2 ? 1 1 ? 1 3 ? 2 3 ? 2 2 ? 3 3 ? 1 4 ? 2 4 ? 3 4 ? 4 4 ? 1 5 ? 3 5 ? 2 5 ? 1 6 ? 3 6 ? 5 6 ? 5 5 ? 6 6 ? 1 7 ? 4 7 ? 4 6 ? 6 7 ? 7 7 ? 1 8 ? 4 8 ? 6 8 ? 5 8 ? 5 7 ? 1 9 ? 5 9 ? 7 9 ? 7 8 ? 8 9 ? 8 8 ? 1 10 ? 5 10 ? 8 10 ? 9 10 ? 9 9 ? 10 10 ? 1 11 ? 6 11 ? 6 10 ? 9 11 ? 10 11 ? 11 11 ? 1 12 ? 6...
result:
wrong answer Too many queries.