Submission #1190239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190239		anmattroi	Art Collections (BOI22_art)	C++17	35 / 100	90 ms	420 KiB

art

#include "art.h"
#include <bits/stdc++.h>

using namespace std;

void solve(int N) {

    vector<int> a(N);
    iota(a.begin(), a.end(), 1);

    function<void(int, int)> ftw = [&](int L, int R) {
        if (L == R) return;
        if (L + 1 == R) {
            int cr = publish(a);
            swap(a[L], a[R]);
            int nex = publish(a);
            if (nex > cr) swap(a[L], a[R]);
            return;
        }
        int mid = (L + R) >> 1;
        ftw(L, mid);
        ftw(mid+1, R);
        int szL = L, szR = mid+1;

        vector<int> T;
        while (szL <= mid && szR <= R) {
            vector<int> o;
            for (int i = 0; i < L; i++) o.emplace_back(a[i]);
            for (int i : T) o.emplace_back(i);
            int D = o.size();
            o.emplace_back(a[szL]);
            o.emplace_back(a[szR]);

            for (int i = szL+1; i <= mid; i++) o.emplace_back(a[i]);
            for (int i = szR+1; i <= R; i++) o.emplace_back(a[i]);

            for (int i = R+1; i < N; i++) o.emplace_back(a[i]);

            int A = publish(o);
            swap(o[D], o[D+1]);
            int B = publish(o);
            if (A < B) {
                T.emplace_back(a[szL]);
                ++szL;
                swap(o[D], o[D+1]);
            } else {
                T.emplace_back(a[szR]);
                ++szR;
            }
        }
        for (int i = szL; i <= mid; i++) T.emplace_back(a[i]);
        for (int i = szR; i <= R; i++) T.emplace_back(a[i]);

        for (int i = L; i <= R; i++) a[i] = T[i-L];
    };

    ftw(0, N-1);
    answer(a);
}
/*
5
3 1 4 2 5
*/

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30