Submission #891320

#	Time	Username	Problem	Language	Result	Execution time	Memory
891320		coldEr66	Monster Game (JOI21_monster)	C++17	100 / 100	53 ms	848 KiB

monster

#include "monster.h"
#include <iostream>

using namespace std;

#define ALL(a) begin(a), end(a)
#define eb emplace_back

namespace {

bool example_variable;

}  // namespace

const int maxn = 1e3;

vector<int> id;

void mrg(int l, int r) {
    if (l == r-1) return;
    int mid = l + r >> 1;
    mrg(l, mid), mrg(mid, r);
    
    vector<int> tmp;
    for (int i = l, j = mid; i - l + j - mid < r - l;) {
        if (i < mid && (j == r || Query(id[j], id[i]))) {
            tmp.eb(id[i]);
            ++i;
        }
        else {
            tmp.eb(id[j]);
            ++j;
        }
    }
    for (int i = l; i < r; ++i) id[i] = tmp[i-l];
}

std::vector<int> Solve(int N) {
    id.resize(N);
    for (int i = 0; i < N; ++i) id[i] = i;
    mrg(0, N);

    int tr = min(15, N);

    vector<int> cnt(N);

    for (int i = 0; i < tr; ++i) {
        for (int j = i + 1; j < tr; ++j) {
            if (Query(id[i], id[j])) ++cnt[i];
            else ++cnt[j];
        }
    }
    
    int zero = -1;
    for (int i = 0; i < tr; ++i) {
        if (cnt[i] != 1) continue;
        if (zero == -1) zero = i;
        else if (!Query(id[zero], id[i])) zero = i;
    }

    std::vector<int> T(N);
    int st = 0, idx = 0;
    while (st < N) {
        int nxt = zero;
        for (int i = nxt; i >= st; --i) T[id[i]] = idx++;

        if (nxt + 1 < N) {
            ++nxt;
            while (Query(id[nxt], id[st])) ++nxt;
        }

        st = zero + 1;
        zero = nxt;
    }

    return T;
}

Compilation message (stderr)

monster.cpp: In function 'void mrg(int, int)':
monster.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid = l + r >> 1;
      |               ~~^~~
monster.cpp: At global scope:
monster.cpp:11:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   11 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

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