Submission #1273798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273798		TakeMe	Zagonetka (COI18_zagonetka)	C++20	0 / 100	26 ms	432 KiB

zagonetka

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>

// Testing

void print_permutation(const std::vector<int>& p, int n) {
    for (int i = 1; i <= n; ++i) {
        std::cout << p[i] << (i == n ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // Fast I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
    }

    std::vector<std::vector<bool>> adj(n + 1, std::vector<bool>(n + 1, false));

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            std::vector<int> q = p;
            std::swap(q[i], q[j]);

            std::cout << "query ";
            print_permutation(q, n);

            int response;
            std::cin >> response;

            if (response == 0) {
                if (p[i] < p[j]) {
                    adj[i][j] = true;
                } else {
                    adj[j][i] = true;
                }
            }
        }
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (adj[i][k] && adj[k][j]) {
                    adj[i][j] = true;
                }
            }
        }
    }

    std::vector<int> a(n + 1);
    std::vector<int> in_degree(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (adj[i][j]) {
                in_degree[j]++;
            }
        }
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> pq_a;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            pq_a.push(i);
        }
    }

    int current_val = 1;
    while (!pq_a.empty()) {
        int u = pq_a.top();
        pq_a.pop();

        a[u] = current_val++;

        for (int v = 1; v <= n; ++v) {
            if (adj[u][v]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    pq_a.push(v);
                }
            }
        }
    }

    std::vector<int> b(n + 1);
    for (int i = 1; i <= n; ++i) {
        in_degree[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (adj[i][j]) {
                in_degree[j]++;
            }
        }
    }

    std::priority_queue<int> pq_b;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            pq_b.push(i);
        }
    }

    current_val = 1;
    while (!pq_b.empty()) {
        int u = pq_b.top();
        pq_b.pop();

        b[u] = current_val++;

        for (int v = 1; v <= n; ++v) {
            if (adj[u][v]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    pq_b.push(v);
                }
            }
        }
    }

    std::cout << "end" << std::endl;
    print_permutation(a, n);
    print_permutation(b, n);

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51