Submission #501713

#	Time	Username	Problem	Language	Result	Execution time	Memory
501713		amunduzbaev	Monster Game (JOI21_monster)	C++17	100 / 100	104 ms	536 KiB

monster

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

#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
 
bool qq(int a, int b) {
  return Query(a, b);
}
 
vector<int> Solve(int n) {
	function<vector<int>(int, int)> merge = [&](int l, int r){
		if(l == r) return vector<int>{l};
		int m = (l + r) >> 1;
		vector<int> lx = merge(l, m), rx = merge(m+1, r), res;
		l = 0, r = 0;
		while(l < (int)lx.size() || r < (int)rx.size()){
			if(l < (int)lx.size() && r < (int)rx.size()){
				//~ cout<<rx[r]<<" "<<lx[l]<<"\n";
				if(qq(lx[l], rx[r])) res.push_back(rx[r++]);
				else res.push_back(lx[l++]);
			} else if(l < (int)lx.size()){
				res.push_back(lx[l++]);
			} else {
				res.push_back(rx[r++]);
			}
		}
		
		return res;
	};
	
	vector<int> a = merge(0, n - 1);
	//~ for(int i=0;i<n;i++) cout<<a[i]<<" ";
	//~ cout<<"\n";
	int k = min(11, n);	
	vector<int> in(k);
	for(int i=0;i<k;i++){
		for(int j=i+1;j<k;j++){
			if(qq(a[i], a[j])) in[i]++;
			else in[j]++;
		}
	}
	
	vector<int> tt;
	int mn = 1e9;
	for(int i=0;i<k;i++){
		if(in[i] < mn) mn = in[i], tt = {i};
		else if(in[i] == mn) tt.push_back(i);
	}
	
	int pos = tt[0];
	if((int)tt.size() > 1 && qq(a[tt[1]], a[tt[0]])){
		pos = tt[1];
	}
	
	vector<int> res;
	for(int i=pos;~i;i--){
		res.push_back(a[i]);
	}
	
	int last = 0, l = pos + 1;
	while(l < n){
		int r = l;
		while(r < n && qq(a[r], a[last])) r++;
		for(int i=r;i>=l;i--) res.push_back(a[i]);
		last = l, l = r + 1;
	}
	
	//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
	//~ cout<<"\n";
	
	vector<int> inv(n);
	for(int i=0;i<n;i++) inv[res[i]] = i;
	return inv;
}

/*

5
3 1 4 2 0

*/

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