Submission #1217456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217456		og_matveychick1	Meetings (JOI19_meetings)	C++20	100 / 100	876 ms	920 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"

using namespace std;

mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rn(4);

void answer(int a, int b) {
    Bridge(min(a, b), max(a, b));
}

int n;

void go(int l, int r, vector<int> b, vector<int> &pt) {
    if (b.size() == 0) {
        pt.push_back(r);
        return;
    }
    if (b.size() == 1) {
        pt.push_back(b[0]);
        pt.push_back(r);
        return;
    }
    shuffle(b.begin(), b.end(), rn);
    int v = b.back();
    b.pop_back();
    vector<int> L, R;
    for (auto x: b) {
        if (Query(l, x, v) == x) L.push_back(x);
        else R.push_back(x);
    }
    go(l, v, L, pt);
    go(v, r, R, pt);
}

void go(int v, vector<int> a) {
    shuffle(a.begin(), a.end(), rn);
    int u = a.back();
    a.pop_back();
    vector<int> pt{v};
    vector<int> b;
    map<int, vector<int>> ma;
    for (auto x: a) {
        int w = Query(v, x, u);
        if (w == x) b.push_back(x);
        else ma[w].push_back(x);
    }
    for (auto x: b) a.erase(find(a.begin(), a.end(), x));
    go(v, u, b, pt);
    for (int i = 1; i < pt.size(); i++) answer(pt[i - 1], pt[i]);
    for (auto [w, c]: ma) go(w, c);
}

void Solve(int _n) {
    n = _n;
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    shuffle(a.begin(), a.end(), rn);
    int v = a.back();
    a.pop_back();
    go(v, a);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71