QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489508 | #8819. CNOI Knowledge | liangbowen | WA | 28ms | 5568kb | C++14 | 1.3kb | 2024-07-24 20:45:33 | 2024-07-24 20:45:34 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define mems(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double wisdom;
unordered_map <ull, int> lst;
int ans[1005], tot[1005], cf[1005]; //tot[]: 区间内本质不同子串个数
inline void add(int l, int r) {cf[l]++, cf[r + 1]--;}
inline int ask(int l, int r) {cout << "? " << l << ' ' << r << endl; int x; cin >> x; return x;}
int FIND(int l, int r) {
int R = r;
while (l < r) {int mid = (l + r) >> 1; (tot[mid] + (R - mid + 1) == ask(mid, R)) ? (r = mid) : (l = mid + 1);}
return r;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, idx; cin >> n, tot[1] = lst[ans[1] = idx = 1] = 1;
for (int i = 2; i <= n; i++) {
ull x = 0; int p = FIND(1, i);
ans[i] = (p == 1 ? ++idx : ans[p - 1]);
for (int j = 1; j <= i; j++) cf[j] = 0;
for (int j = i; j; j--) x = x * 7113846 + ans[j], add(lst[x] + 1, j), lst[x] = j;
for (int j = 1; j <= i; j++) cf[j] += cf[j - 1]; for (int j = 1; j <= i; j++) tot[j] += cf[j];
}
cout << "! "; for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
12 3 3 6 6 10 6 10 15 10 15 21 10 20 15 14 6 9 14 27 34 43 19 5 2 19 5 8 25 9 13 19
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 2 6 ? 1 6 ? 4 7 ? 2 7 ? 3 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 3 9 ? 2 9 ? 1 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 8 11 ? 6 12 ? 9 12 ? 8 12 ? 7 12 ! 1 2 3 4 5 6 2 5 7 7 5 6
result:
ok Accepted. 31 queries used.
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 5568kb
input:
1000 3 2 3 2 5 7 11 8 2 7 2 11 5 7 11 5 3 15 5 2 15 3 2 19 4 2 17 4 2 20 4 2 15 4 2 23 9 13 15 23 11 5 3 31 11 5 3 36 11 5 2 45 15 3 2 48 15 5 7 11 58 16 5 2 59 16 5 8 69 21 8 2 69 20 8 3 5 79 20 8 2 76 20 8 3 5 87 26 8 3 5 88 26 8 2 100 24 8 3 5 98 24 8 2 111 31 11 3 2 108 33 11 5 7 120 33 11 5 2 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 10 16 ? 9 16 ? 9 17 ? 13 17 ? 15 17 ? 16 17 ? 9...
result:
wrong answer Wrong Answer.