Submission #421327

#	Time	Username	Problem	Language	Result	Execution time	Memory
421327		jamezzz	Monster Game (JOI21_monster)	C++17	100 / 100	136 ms	320 KiB

monster

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

namespace{

vector<int> a,t,s,ans;
vector<ii> p;

void mergesort(int l,int r){
	if(l==r)return;
	int m=(l+r)/2;
	mergesort(l,m);
	mergesort(m+1,r);
	t.clear();
	int cl=l,cr=m+1;
	while(cl<=m||cr<=r){
		if(cl>m||(cr<=r&&Query(a[cl],a[cr])))t.pb(a[cr++]);
		else t.pb(a[cl++]);
	}
	for(int i=l;i<=r;++i)a[i]=t[i-l];
	t.clear();
}

void small(int n){//brute force the first n elements
	for(int i=0;i<n;++i){
		int cnt=0;
		for(int j=0;j<n;++j){
			if(j==i)continue;
			cnt+=Query(s[i],s[j]);
		}
		p.pb(cnt,s[i]);
	}
	sort(all(p));
	if(Query(p[1].se,p[0].se))swap(p[1],p[0]);
	if(Query(p[n-1].se,p[n-2].se))swap(p[n-2],p[n-1]);
	for(int i=0;i<n;++i)s[i]=p[i].se;
}
}

vector<int> Solve(int n){
	for(int i=0;i<n;++i)a.pb(i);
	mergesort(0,n-1);
	for(int i=0;i<min(n,10);++i)s.pb(a[i]);
	small(min(n,10));
	a.erase(find(all(a),s[0]));
	a.insert(a.begin(),s[0]);
	ans.resize(n);
	int cur=0;
	for(int i=cur+1;i<n;++i){
		if(Query(a[cur],a[i])){
			reverse(a.begin()+cur+1,a.begin()+i+1);
			cur=i;
		}
	}
	for(int i=0;i<n;++i)ans[a[i]]=i;
	return ans;
}

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