Submission #679829

#	Time	Username	Problem	Language	Result	Execution time	Memory
679829		bashkort	Monster Game (JOI21_monster)	C++17	100 / 100	98 ms	332 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);

    auto merge_sort = [&](auto self, vector<int> a) -> vector<int> {
        if (a.size() == 1) {
            return a;
        }
        int mid = a.size() / 2;
        auto L = self(self, vector(a.begin(), a.begin() + mid));
        auto R = self(self, vector(a.begin() + mid, a.end()));
        a.clear();
        int i = 0, j = 0;
        while (i < L.size() || j < R.size()) {
            if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
                a.push_back(L[i++]);
            } else {
                a.push_back(R[j++]);
            }
        }
        return a;
    };

    ord = merge_sort(merge_sort, ord);

    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();
    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;
        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;
}

Compilation message (stderr)

monster.cpp: In instantiation of 'Solve(int)::<lambda(auto:23, std::vector<int>)> [with auto:23 = Solve(int)::<lambda(auto:23, std::vector<int>)>]':
monster.cpp:32:37:   required from here
monster.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while (i < L.size() || j < R.size()) {
      |                ~~^~~~~~~~~~
monster.cpp:22:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while (i < L.size() || j < R.size()) {
      |                                ~~^~~~~~~~~~
monster.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
      |                 ~~^~~~~~~~~~
monster.cpp:23:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
      |                                  ~~^~~~~~~~~~~

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