Submission #545735

#	Time	Username	Problem	Language	Result	Execution time	Memory
545735		alextodoran	Monster Game (JOI21_monster)	C++17	100 / 100	84 ms	4260 KiB

monster

#include <bits/stdc++.h>

using namespace std;

bool Query (int a, int b);

vector <vector <int>> cmp;
bool ask (int a, int b) {
    if (a > b) {
        swap(a, b);
        if (cmp[a][b] == -1) {
            cmp[a][b] = Query(a, b);
        }
        return !cmp[a][b];
    } else {
        if (cmp[a][b] == -1) {
            cmp[a][b] = Query(a, b);
        }
        return cmp[a][b];
    }
}

void mergeSort (vector <int> :: iterator l, vector <int> :: iterator r) {
    int len = r - l;
    if (len != 1) {
        int mid = len / 2;
        mergeSort(l, l + mid);
        mergeSort(l + mid, r);
        vector <int> aux (len);
        merge(l, l + mid, l + mid, r, aux.begin(), [&] (const int &i, const int &j) {
            return ask(j, i);
        });
        copy(aux.begin(), aux.end(), l);
    }
}

vector <int> Solve (int N) {
    cmp = vector <vector <int>> (N, vector <int> (N, -1));
    vector <int> order (N);
    iota(order.begin(), order.end(), 0);
    mergeSort(order.begin(), order.end());
    int K = min(N, 10);
    vector <int> cnt (K, 0);
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            if (i != j) {
                cnt[i] += ask(order[i], order[j]);
            }
        }
    }
    vector <int> aux (K);
    iota(aux.begin(), aux.end(), 0);
    sort(aux.begin(), aux.end(), [&] (const int &i, const int &j) {
        return cnt[i] < cnt[j];
    });
    int currMin = (ask(order[aux[0]], order[aux[1]]) == true ? aux[0] : aux[1]);
    reverse(order.begin(), order.begin() + currMin + 1);
    while (currMin + 1 < N) {
        int nextMin = currMin + 1;
        while (ask(order[currMin], order[nextMin]) == false) {
            nextMin++;
        }
        reverse(order.begin() + currMin + 1, order.begin() + nextMin + 1);
        currMin = nextMin;
    }
    vector <int> ret (N);
    for (int i = 0; i < N; i++) {
        ret[order[i]] = i;
    }
    return ret;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75