Submission #1201742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201742		madamadam3	Art Collections (BOI22_art)	C++20	0 / 100	1 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;

/*
    where[x] vector of length N+1, stores the position of collection x in the permutation (-1 if we dont know)
    who[pos] vector of length N+1, stores which collection is currently at position pos in the permutation (-1 if we dont know)
*/

vi invert(vi &where) {
    vi who(n+1, -1);
    for (int i = 1; i <= n; i++) {
        if (where[i] != -1) who[where[i]] = i;
    }

    return who;
}

struct State {
    vi where, who;
    set<int> unused;
};

vi make_perm(State state) {
    vi rt(n, -1);

    for (int i = 1; i <= n; i++) {
        if (state.where[i] == -1) continue;
        rt[state.where[i] - 1] = i;
    }

    int cur_pos = 0;
    for (auto &el : state.unused) {
        while (rt[cur_pos] != -1) cur_pos++;
        rt[cur_pos] = el;
    }

    return rt;
}

int best_at(State state, int pos) {
    auto ns = state;
    int best = INT_MAX, best_node = -1;

    for (int i = 1; i <= n; i++) {
        if (!state.unused.count(i)) continue;

        ns.unused.erase(i);
        ns.where[i] = pos;
        ns.who = invert(ns.where);
        int res = publish(make_perm(ns));
        ns.where[i] = -1;
        ns.who = invert(ns.where);
        ns.unused.insert(i);

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

    return best_node;
}

void solve(int N) {
    n = N;

    // find the best node for each index and recompute state
    State state;
    for (int i = 1; i <= n; i++) state.unused.insert(i);
    state.where.assign(n+1,-1);
    state.who.assign(n+1,-1);

    for (int i = 1; i <= n; i++) {
        int best = best_at(state, i);
        state.unused.erase(best);
        state.where[best] = i;
        state.who = invert(state.where);
    }

    vector<int> vorder(n);
    for (int i = 1; i <= n; i++) {
        vorder[i-1] = state.who[i];
    }
    answer(vorder);
}

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