Submission #1146351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146351		hmm789	Monster Game (JOI21_monster)	C++20	89 / 100	35 ms	1088 KiB

monster

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

map<pair<int, int>, int> mp;
bool query(int a, int b) {
    if(mp.count({a,b})) return mp[{a,b}];
    else if(mp.count({b,a})) return !mp[{b,a}];
    else return mp[{a,b}] = Query(a, b);
}

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: 64 / 75