QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489426 | #8819. CNOI Knowledge | Hunster | WA | 0ms | 3640kb | C++20 | 2.3kb | 2024-07-24 20:03:52 | 2024-07-24 20:03:52 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int N = 1003;
struct SAM {
struct Node {
int nxt[26];
int len, fail;
};
Node node[2 * N];
int tot, rt, lst[N];
int clone(int p) {
int u = ++tot;
node[u] = node[p];
return u;
}
void build(int n, int a[]) {
tot = 0;
rt = ++tot;
for (int &v : node[rt].nxt) v = rt;
lst[0] = rt;
for (int i = 1; i <= n; i++) {
int w = a[i];
int cur = clone(lst[i - 1]);
node[cur].len = node[lst[i - 1]].len + 1;
int p = lst[i - 1];
for (; p && node[p].nxt[w] == rt; p = node[p].fail)
node[p].nxt[w] = cur;
if (!p) node[cur].fail = rt;
else {
int q = node[p].nxt[w];
if (node[q].len == node[p].len + 1)
node[cur].fail = q;
else {
int r = clone(q);
node[r].len = node[p].len + 1;
node[q].fail = node[cur].fail = r;
for (; p && node[p].nxt[w] == q; p = node[p].fail)
node[p].nxt[w] = r;
}
}
lst[i] = cur;
}
}
};
SAM sam;
int n, a[N];
int main() {
std::cin.sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
int t = 0;
for (int i = 1; i <= n; i++) {
const auto query = [&](int l, int r) {
int res = 0;
if (r < i) {
sam.build(r - l + 1, a + l - 1);
for (int i = 1; i <= sam.tot; i++) res += sam.node[i].len - sam.node[sam.node[i].fail].len;
}
else {
std::cout << "? " << l << " " << r << std::endl;
std::cin >> res;
}
return res;
};
int l = 0, r = i - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (query(mid, i - 1) + (i - mid + 1) == query(mid, i)) r = mid - 1;
else l = mid;
}
if (l == 0) a[i] = t++;
else a[i] = a[l];
}
std::cout << "! ";
for (int i = 1; i <= n; i++) std::cout << (char)('a' + a[i]);
std::cout << std::endl;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3640kb
input:
12 3 6 6 10 10 15 10 21 15 27 20 14 6 9 20 34 43 19 9 5 2 25 8 5 25 9 19
output:
? 1 2 ? 1 3 ? 2 4 ? 1 4 ? 2 5 ? 1 5 ? 3 6 ? 1 6 ? 3 7 ? 1 7 ? 2 7 ? 4 8 ? 6 8 ? 5 8 ? 4 9 ? 2 9 ? 1 9 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 5 11 ? 8 11 ? 9 11 ? 6 12 ? 9 12 ? 7 12 ! abcdefbeggef
result:
wrong answer format Expected integer, but "abcdefbeggef" found