제출 #1222781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222781		thinknoexit	Zagonetka (COI18_zagonetka)	C++20	100 / 100	27 ms	452 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) {
    // find topological order
    adj2[j].push_back(i);
    for (int k = 1;k <= n;k++) p2[k] = p[k];
    for (int k = i;k <= j;k++) {
        for (auto& x : adj2[k]) {
            if (x <= j) deg[x]++;
        }
    }
    queue<int> q;
    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);
            }
        }
    }
    cout << "end" << endl;
    for (int i = 1;i <= n;i++) {
        for (auto& x : adj2[i]) {
            rev[pos[x]].push_back(pos[i]);
            deg1[pos[i]]++;
            adj[pos[i]].push_back(pos[x]);
            deg2[pos[x]]++;
        }
    }
    // calculate answer
    {
        priority_queue<int> pq; // largest
        for (int i = 1;i <= n;i++) {
            if (deg1[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 (--deg1[x] == 0) {
                    pq.push(x);
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            cout << res[i] << ' ';
        }
        cout << endl;
    }
    {
        priority_queue<int> pq; // largest
        for (int i = 1;i <= n;i++) {
            if (deg2[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 (--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
6
1 2 3 4 5 6
*/

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