Submission #1240480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240480		trantrungkein	Monster Game (JOI21_monster)	C++20	100 / 100	24 ms	408 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
#define all(a) (a).begin(),(a).end()
#define bg(a) (a).begin()
#define ed(a) (a).end()
#define sz(a) (int)(a).size()
#define ii pair<int,int>
#define fi first
#define se second
vector<int> sort(vector<int> cr){
    if(sz(cr)==1) return cr;
    int m=sz(cr)/2;
    vector<int> a(bg(cr),bg(cr)+m),b(bg(cr)+m,ed(cr));
    a=sort(a); b=sort(b);
    int ap=0,bp=0;
    for(int i=0;i<sz(cr);++i){
        if(ap==sz(a)) cr[i]=b[bp++];
        else if(bp==sz(b)) cr[i]=a[ap++];
        else if(Query(a[ap],b[bp])) cr[i]=b[bp++];
        else cr[i]=a[ap++];
    }
    return cr;
}
vector<int> Solve(int N){
    vector<int> ans(N);
    iota(all(ans),0);
    ans=sort(ans);
    vector<ii> win(min(N,10));
    for(int i=0;i<min(N,10);++i){
        win[i].se=ans[i];
        for(int j=i+1;j<min(N,10);++j)
            if(Query(ans[i],ans[j])) win[i].fi++;
            else win[j].fi++;
    }
    sort(all(win));
    int bk=win[0].se;
    if(Query(win[1].se,win[0].se)) bk=win[1].se;
    ans.erase(find(all(ans),bk));
    ans.insert(bg(ans),bk);
    for(int i=1;i<N;++i){
        int j=i;
        while(j<N&&Query(ans[j],bk)) j++;
        reverse(bg(ans)+i,bg(ans)+min(j+1,N));
        i=j; bk=ans[i];
    }
    vector<int> out(N);
    for(int i=0;i<N;++i) out[ans[i]]=i;
    return out;
}

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