QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#800700#8819. CNOI KnowledgeNotNotToday#WA 0ms3576kbC++201.5kb2024-12-06 14:40:392024-12-06 14:40:40

Judging History

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

  • [2024-12-06 14:40:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3576kb
  • [2024-12-06 14:40:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

#ifdef LOCAL
    vector<int> arr(n);
    for (int &x : arr) {
        cin >> x;
    }
#endif

    auto ask = [&](int l, int r) {
#ifdef LOCAL
        vector<int> u(arr.begin() + l - 1, arr.begin() + r);
        sort(u.begin(), u.end());
        return unique(u.begin(), u.end()) - u.begin();
#else
        cout << "? " << l << " " << r << endl;
        int res;
        cin >> res;
        return res;
#endif
    };

    vector<int> a(n + 1);
    auto stupid = [&](int l, int r) -> int {
        int res = 0;
        for (int i = l; i <= r; ++i) {
            if (a[i] < l) {
                res += 1;
            }
        }
        return res;
    };

    int x = 0;
    vector<int> ans(n + 1);
    for (int i = 2; i <= n; ++i) {
        int lo = 0, hi = i;
        while (lo + 1 < hi) {
            int mid = lo + hi >> 1;
            if (ask(mid, i) == stupid(mid, i - 1)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        a[i] = lo;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0) {
            ans[i] = ++x;
        } else {
            ans[i] = ans[a[i]];
        }
    }

    cout << "! ";
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3576kb

input:

12
3
6
6
10
10
15
10
21
15
27
14
26
34
20
34
43
19
42
52
25
51
62
25
50
72

output:

? 1 2
? 1 3
? 2 4
? 1 4
? 2 5
? 1 5
? 3 6
? 1 6
? 3 7
? 1 7
? 4 8
? 2 8
? 1 8
? 4 9
? 2 9
? 1 9
? 5 10
? 2 10
? 1 10
? 5 11
? 2 11
? 1 11
? 6 12
? 3 12
? 1 12
! 1 2 3 4 5 6 7 8 9 10 11 12 

result:

wrong answer Wrong Answer.