Submission #1201730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201730		madamadam3	Art Collections (BOI22_art)	C++20	0 / 100	0 ms	408 KiB

art

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

using namespace std;
using vi = vector<int>;

#define all(x) (x).begin(), (x).end()
#define mp(x) iota(all((x)), 1)

int n;

vi make_perm(vi &order) {
    vi rt(n, -1);
    set<int> avail; for (int i = 1; i <= n; i++) avail.insert(i);

    for (int i = 1; i <= order.size(); i++) {
        avail.erase(order[i - 1]);
        rt[i-1] = order[i - 1]; 
    }

    for (int i = 1; i <= n; i++) {
        if (rt[i-1] != -1) continue;
        rt[i-1] = *avail.begin();
        avail.erase(avail.begin());
    }

    return rt;
}


int best_at(vi &order, set<int> used) {
    int pos = order.size() + 1;
    vi cur_order = order;

    int best = INT_MAX, best_idx = -1;
    for (int i = 1; i <= n; i++) {
        if (used.count(i)) continue;
        cur_order.push_back(i);
        int res = publish(make_perm(cur_order));
        cur_order.pop_back();

        if (res <= best) {
            best = res;
            best_idx = i;
        }
    }

    return best_idx;
}

void solve(int N) {
    n = N;
    vi order;
    set<int> used;

    while (order.size() < n) {
        int best = best_at(order, used);
        order.push_back(best);
        used.insert(best);
    }

    answer(order);
}

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