Submission #1340093

#TimeUsernameProblemLanguageResultExecution timeMemory
1340093model_codeKoreografija (COI24_koreografija)C++20
100 / 100
48 ms4356 KiB
#include <algorithm>
#include <array>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

namespace {

constexpr int N = 1000;

int cache_answer[N][N];
int rank_at_pos[N];

int ask(int l, int r) {
    if (l > r) {
        return 0;
    }
    int &memo = cache_answer[l][r];
    if (memo != -1) {
        return memo;
    }

    cout << "? " << (l + 1) << ' ' << (r + 1) << '\n';
    cout.flush();

    cin >> memo;
    memo &= 1;
    return memo;
}

// Returns true iff value at position old_pos is greater than value at position new_pos.
bool greater_than_new(int old_pos, int new_pos) {
    int parity = ask(old_pos, new_pos) ^ ask(old_pos + 1, new_pos);

    int known = 0;
    for (int pos = old_pos + 1; pos < new_pos; ++pos) {
        if (rank_at_pos[pos] < rank_at_pos[old_pos]) {
            known ^= 1;
        }
    }

    return (parity ^ known) != 0;
}

}  // namespace

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

    memset(cache_answer, -1, sizeof(cache_answer));
    fill(rank_at_pos, rank_at_pos + N, -1);

    vector<int> order;
    order.reserve(N);
    order.push_back(0);
    rank_at_pos[0] = 1;

    for (int pos = 1; pos < N; ++pos) {
        int lo = 0;
        int hi = static_cast<int>(order.size());

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (greater_than_new(order[mid], pos)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        order.insert(order.begin() + lo, pos);
        for (int i = 0; i < static_cast<int>(order.size()); ++i) {
            rank_at_pos[order[i]] = i + 1;
        }
    }

    cout << "!\n";
    cout.flush();
    for (int i = 0; i < N; ++i) {
        if (i) {
            cout << ' ';
        }
        cout << rank_at_pos[i];
    }
    cout << '\n';
    cout.flush();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...