Submission #850985

#	Time	Username	Problem	Language	Result	Execution time	Memory
850985		Cyanmond	Zagonetka (COI18_zagonetka)	C++17	100 / 100	46 ms	716 KiB

zagonetka

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

void answer(vector<int> P, vector<int> Q) {
    cout << "end" << endl;
    rep(i, 0, (int)P.size()) cout << P[i] + 1 << (i == (int)P.size() - 1 ? '\n' : ' ');
    rep(i, 0, (int)Q.size()) cout << Q[i] + 1 << (i == (int)Q.size() - 1 ? '\n' : ' ');
    cout << flush;
}

bool ask(vector<int> P) {
    cout << "query ";
    rep(i, 0, (int)P.size()) {
        cout << P[i] + 1 << (i == (int)P.size() - 1 ? '\n' : ' ');
    }
    cout << flush;
    int res;
    cin >> res;
    return res ? true : false;
}

void main_() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (auto &e : P) {
        cin >> e;
        --e;
    }
    vector<int> rP(N);
    rep(i, 0, N) rP[P[i]] = i;

    vector<vector<int>> C(N);

    auto makeCut = [&](int a, int b) -> pair<vector<int>, vector<int>> {
        vector<int> x;
        vector<bool> isUsed(N);
        queue<int> que;
        que.push(a);
        isUsed[a] = true;
        while (not que.empty()) {
            const auto f = que.front();
            que.pop();
            if (P[f] > P[b]) continue;
            x.push_back(f);
            for (const auto t : C[f]) {
                if (isUsed[t]) continue;
                isUsed[t] = true;
                que.push(t);
            }
        }
        if (find(ALL(x), b) != x.end()) {
            return {{}, {}};
        } else {
            vector<int> y;
            rep(i, P[a], P[b] + 1) {
                if (find(ALL(x), rP[i]) == x.end()) y.push_back(rP[i]);
            }
            return {x, y};
        }
    };

    rep(w, 1, N) {
        rep(lx, 0, N - w) {
            int r = lx + w;
            int l = lx;

            const auto [x, y] = makeCut(rP[l], rP[r]);
            if (x.empty()) {
                C[rP[l]].push_back(rP[r]);
            } else {
                // query
                auto p = P;
                // const int a = (int)x.size(), b = (int)y.size();
                int v = l;
                for (const auto e : y) {
                    p[e] = v++;
                }
                for (const auto e : x) {
                    p[e] = v++;
                }
                const auto res = ask(p);
                if (not res) {
                    C[rP[l]].push_back(rP[r]);
                }
            }
        }
    }

    vector<vector<int>> rC(N);
    rep(i, 0, N) {
        for (const auto t : C[i]) {
            rC[t].push_back(i);
        }
    }

    vector<int> ansA, ansB;
    {
        vector<int> val(N, -1);
        int nowVal = 0;
        auto mkMin = [&](auto &&self, const int v) -> void {
            assert(val[v] == -1);
            vector<int> vs;
            queue<int> que;
            que.push(v);
            vector<bool> isUsed(N);
            isUsed[v] = true;
            while (not que.empty()) {
                const auto f = que.front();
                que.pop();
                vs.push_back(f);
                for (const auto t : rC[f]) {
                    if (isUsed[t]) continue;
                    if (val[t] != -1)  continue;
                    isUsed[t] = true;
                    que.push(t);
                }
            }

            vs.erase(find(ALL(vs), v));
            while (not vs.empty()) {
                const int mn = *min_element(ALL(vs));
                self(self, mn);
                vector<int> nextVs;
                for (const auto e : vs) if (val[e] == -1) nextVs.push_back(e);
                vs = move(nextVs);
            }
            val[v] = nowVal++;
        };
        rep(i, 0, N) {
            if (val[i] == -1) {
                mkMin(mkMin, i);
            }
        }
        ansA = val;
    }
    {
        vector<int> val(N, -1);
        int nowVal = N - 1;
        auto mkMax = [&](auto &&self, const int v) -> void {
            assert(val[v] == -1);
            vector<int> vs;
            queue<int> que;
            que.push(v);
            vector<bool> isUsed(N);
            isUsed[v] = true;
            while (not que.empty()) {
                const auto f = que.front();
                que.pop();
                vs.push_back(f);
                for (const auto t : C[f]) {
                    if (isUsed[t]) continue;
                    if (val[t] != -1)  continue;
                    isUsed[t] = true;
                    que.push(t);
                }
            }

            vs.erase(find(ALL(vs), v));
            while (not vs.empty()) {
                const int mn = *min_element(ALL(vs));
                self(self, mn);
                vector<int> nextVs;
                for (const auto e : vs) if (val[e] == -1) nextVs.push_back(e);
                vs = move(nextVs);
            }
            val[v] = nowVal--;
        };
        rep(i, 0, N) {
            if (val[i] == -1) {
                mkMax(mkMax, i);
            }
        }
        ansB = val;
    }
    answer(ansA, ansB);
}

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

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