Submission #679828

#	Time	Username	Problem	Language	Result	Execution time	Memory
679828		bashkort	Monster Game (JOI21_monster)	C++17	98 / 100	111 ms	1700 KiB

monster

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

using namespace std;


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

    mt19937 rnd(228);
    shuffle(ord.begin(), ord.end(), rnd);


    map<pair<int, int>, bool> asked;
    auto ask = [&](int i, int j) {
        if (!asked.count({i, j})) {
            asked[{i, j}] = Query(i, j);
            asked[{j, i}] = !asked[{i, j}];
        }
        return asked[{i, j}];
    };
    
    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
        return !ask(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 (ask(ord[i], ord[j])) {
                win[i] += 1;
            } else {
                win[j] += 1;
            }
        }
    }

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

    int x = ask(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 (ask(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: 73 / 75