Submission #1061218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061218		ttamx	Monster Game (JOI21_monster)	C++17	0 / 100	60 ms	592 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> Solve(int n){
	vector<int> a(n),b(n);
	function<void(int,int)> msort=[&](int l,int r){
		if(l==r)return;
		int m=(l+r)/2;
		msort(l,m);
		msort(m+1,r);
		for(int i=l,j=m+1,p=l;p<=r;p++){
			if(j>r||(i<=m&&!Query(a[i],a[j]))){
				b[p]=a[i++];
			}else{
				b[p]=a[j++];
			}
		}
		for(int i=l;i<=r;i++)a[i]=b[i];
	};
	iota(a.begin(),a.end(),0);
	msort(0,n-1);
	int st=-1;
	if(Query(a[1],a[0])){
		st=1;
		for(int i=2;i<n;i++){
			if(Query(a[1],a[i])){
				st=-1;
				break;
			}
		}
	}
	if(st==-1){
		st=2;
		while(Query(a[st-1],a[st])||Query(a[st],a[0])){
			st++;
			assert(st<n);
		}
	}
	reverse(a.begin(),a.begin()+st+1);
	for(int i=st+1;i<n;i++){
		int j=i;
		while(!Query(a[i-1],a[j])){
			j++;
			assert(j<n);
		}
		reverse(a.begin()+i,a.begin()+j+1);
		i=j;
	}
	vector<int> ans(n);
	for(int i=0;i<n;i++)ans[a[i]]=i;
	return ans;
}

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