Submission #1146346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146346		hmm789	Monster Game (JOI21_monster)	C++20	86 / 100	31 ms	408 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> Solve(int N) {
    vector<int> a(N), ans(N), opp;
    int mx, prv = 0;
    for(int i = 0; i < N; i++) a[i] = i;
    stable_sort(a.begin(), a.end(), Query);
    for(int i = 1; i < N; i++) if(Query(a[i], a[0])) opp.push_back(i);
    if(opp.size() == 1) {
        int cnt = 0;
        for(int i = 0; i < N; i++) if(i != 1) if(Query(a[i], a[1])) cnt++;
        if(cnt == 1) mx = 1;
        else mx = 0;
    } else {
        mx = opp[opp.size()-2];
    }
    reverse(a.begin(), a.begin()+mx+1);
    while(mx < N) {
        int idx = mx+1;
        while(idx < N && Query(a[mx], a[idx])) idx++;
        prv = mx+1;
        mx = idx;
        reverse(a.begin()+prv, a.begin()+min(N, mx+1));
    }
    for(int i = 0; i < N; i++) ans[a[i]] = N-i-1;
    return ans;
}

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