제출 #1240484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240484		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;
        for(;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