Submission #1271290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271290		wetsponge	Monster Game (JOI21_monster)	C++20	0 / 100	25 ms	440 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> merge(vector <int> A,vector <int> B){
	vector <int> C;
	while(A.size()>0&&B.size()>0){
		if(Query(A.back(),B.back())==0){
			C.push_back(A.back());
			A.pop_back();
		}
		else{
			C.push_back(B.back());
			B.pop_back();	
		}
	}
	while(B.size()>0){
		C.push_back(B.back());
		B.pop_back();
	}
	while(A.size()>0){
		C.push_back(A.back());
		A.pop_back();
	}
	reverse(C.begin(),C.end());
	return C;
}
vector <int> sort(vector <int> v){
	if(v.size()<=1) return v;
	vector <int> A,B;
	for(int i=0;i<v.size()/2;i++){
		A.push_back(v[i]);
	}
	for(int i=v.size()/2;i<v.size();i++){
		B.push_back(v[i]);
	}
	A=sort(A);
	B=sort(B);
	return merge(A,B);
}
std::vector<int> Solve(int N) {
	vector<int> arr;
	for(int i=0;i<N;i++) arr.push_back(i);
	arr=sort(arr);
	reverse(arr.begin(),arr.end());
	// for(int i=0;i<N;i++) cout<<arr[i]<<" ";
	// cout<<endl;
	for(int i=0;i<N;i++){
		if(i==N-1) break;
		if(i==0){
			int cnt=0;
			for(int j=1;j<N;j++) if(Query(arr[0],arr[j])==1) cnt++;
			//cout<<cnt<<endl;
			if(cnt==1) continue;
		}
		//cout<<i<<endl;
		int bg=i;
		if(Query(arr[bg-1],arr[bg])==1) continue;
		//cout<<arr[bg]<<" "<<arr[bg+2]<<" "<<Query(arr[bg],arr[bg+2])<<endl;
		while(bg<N-2&&Query(arr[bg],arr[bg+2])==1){
			bg+=2;
		}
		int r;
		//cout<<i<<" "<<bg<<endl;
		if(bg==i&&bg!=N-1) bg++;
		else{
			if(bg!=N-1&&Query(arr[bg-1],arr[bg+1])==1) bg++;
		}
		if(bg-i+1==3&&bg==N-1){
			//cout<<"YES"<<endl;
			if(Query(arr[i-1],arr[N-1])==1) reverse(arr.begin()+i,arr.begin()+bg+1);
			else reverse(arr.begin()+i,arr.begin()+bg);
		}
		else reverse(arr.begin()+i,arr.begin()+bg+1);
		i=bg;
	}
	// for(int i=0;i<N;i++) cout<<arr[i]<<" ";
	// cout<<endl;
	vector <int> ans(N);
	for(int i=0;i<N;i++) ans[arr[i]]=i;
	// cout<<endl;
	return ans;
}

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