Submission #679826

#	Time	Username	Problem	Language	Result	Execution time	Memory
679826		bashkort	Monster Game (JOI21_monster)	C++17	95 / 100	106 ms	328 KiB

monster

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

using namespace std;

mt19937 rnd(228);

vector<int> Solve(int n) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);

    shuffle(ord.begin(), ord.end(), rnd);
    
    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
        return !Query(i, j);
    });

    int k = min(n, 10);

    vector<int> win(k);

    for (int i = 0; i < k; ++i) {
        for (int j = i + 1; j < k; ++j) {
            if (Query(ord[i], ord[j])) {
                win[i] += 1;
            } else {
                win[j] += 1;
            }
        }
    }

    int fi = min_element(win.begin(), win.end()) - win.begin();
    assert(win.begin() + fi != win.end());
    int se = min_element(win.begin() + fi + 1, win.end()) - win.begin();

    int x = Query(ord[fi], ord[se]) ? fi : se;

    rotate(ord.begin(), ord.begin() + x, ord.begin() + x + 1);

    x = 0;

    for (int i = 1, j = 1; i < n; i = j) {
        while (Query(ord[j], ord[x])) {
            j += 1;
        }

        j += 1;
        reverse(ord.begin() + i, ord.begin() + j);

        x = j - 1;
    }

    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[ord[i]] = i;
    }

    return ans;
}

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