Submission #1222737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222737		thinknoexit	Zagonetka (COI18_zagonetka)	C++20	0 / 100	24 ms	444 KiB

zagonetka

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 111;
int n;
int p[N], p2[N], pos[N];
vector<int> adj[N], adj2[N], rev[N];
int deg[N], deg1[N], deg2[N];
int res[N];
bool vis[N];
int ask(int i, int j) {
    if (i > j) swap(i, j);
    // find topological order
    memset(deg, 0, sizeof deg);
    adj2[j].push_back(i);
    queue<int> q;
    for (int k = 1;k <= n;k++) p2[k] = p[k];
    for (int k = i;k <= j;k++) {
        for (auto& x : adj2[k]) {
            deg[x]++;
        }
    }
    for (int k = i;k <= j;k++) {
        if (deg[k] == 0) q.push(k);
    }
    for (int k = i;k <= j;k++) {
        int v = q.front();
        p2[pos[v]] = k;
        q.pop();
        for (auto& x : adj2[v]) {
            if (x <= j && --deg[x] == 0) {
                q.push(x);
            }
        }
    }
    adj2[j].pop_back();
    cout << "query ";
    for (int k = 1;k <= n;k++) cout << p2[k] << ' ';
    cout << endl;
    int x;
    cin >> x;
    return x;
}
void dfs(int v) {
    vis[v] = 1;
    for (auto& x : adj2[v]) if (!vis[x]) dfs(x);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> p[i];
        pos[p[i]] = i;
    }
    for (int k = 1;k < n;k++) {
        for (int i = 1;i <= n - k;i++) {
            memset(vis, 0, sizeof vis);
            dfs(i);
            if (vis[i + k]) continue;
            if (!ask(i, i + k)) {
                adj2[i].push_back(i + k);
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (auto& x : adj2[i]) {
            adj[pos[i]].push_back(pos[x]);
            deg1[pos[x]]++;
            rev[pos[x]].push_back(pos[i]);
            deg2[pos[i]]++;
        }
    }
    // calculate answer
    cout << "end" << endl;
    {
        priority_queue<int, vector<int>, greater<int>> pq; // largest
        for (int i = 1;i <= n;i++) {
            if (deg1[i] == 0) pq.push(i);
        }
        for (int i = 1;i <= n;i++) {
            int v = pq.top();
            pq.pop();
            res[v] = i;
            for (auto& x : adj[v]) {
                if (--deg1[x] == 0) {
                    pq.push(x);
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            cout << res[i] << ' ';
        }
        cout << endl;
    }
    {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 1;i <= n;i++) {
            if (deg2[i] == 0) pq.push(i);
        }
        for (int i = n;i >= 1;i--) {
            int v = pq.top();
            pq.pop();
            res[v] = i;
            for (auto& x : rev[v]) {
                if (--deg2[x] == 0) {
                    pq.push(x);
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            cout << res[i] << ' ';
        }
        cout << endl;
    }

    return 0;
}
/*
4
3 2 1 4
*/

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