QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489426#8819. CNOI KnowledgeHunsterWA 0ms3640kbC++202.3kb2024-07-24 20:03:522024-07-24 20:03:52

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 20:03:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3640kb
  • [2024-07-24 20:03:52]
  • 提交

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