Submission #423759

#	Time	Username	Problem	Language	Result	Execution time	Memory
423759		patrikpavic2	Monster Game (JOI21_monster)	C++17	100 / 100	157 ms	272 KiB

monster

#include "monster.h"
#include <vector>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <unistd.h>
 
#define PB push_back
 
using namespace std;
 
typedef vector < int > vi;
 
namespace {
 
bool example_variable;
 
void merge_sort(vi &v){
	if((int)v.size() <= 1) return;
	vi A[2];
	for(int i = 0;i < (int)v.size();i++)
		A[i & 1].PB(v[i]);
	merge_sort(A[0]); merge_sort(A[1]);
	v.clear();
	int i = 0, j = 0;
	for(;i < (int)A[0].size() || j < (int)A[1].size();){
		if(i == (int)A[0].size()) v.PB(A[1][j++]);
		else if(j == (int)A[1].size()) v.PB(A[0][i++]); 
		else if(!Query(A[0][i], A[1][j])) v.PB(A[0][i++]);
		else v.PB(A[1][j++]);
	}
}
 
}  // namespace
 
vi Solve(int n) {
	vi v, ret(n); 
	for(int i = 0;i < n;i++)
		v.PB(i);
	random_shuffle(v.begin(), v.end());
	merge_sort(v); 
	int pref = 0, cnt = 0;
	for(int i = 1;i < n && i < 100;i++)
		cnt += Query(v[0], v[i]);
	if(cnt == 1){
		int cnt2 = 0;
		for(int i = 2;i < n && i < 100;i++)
			cnt2 += Query(v[1], v[i]);
		if(cnt2 == 0)
			pref = 1;
		else
			pref = 0;
	}
	else
		pref = cnt;
	int lst = pref;
	reverse(v.begin(), v.begin() + pref + 1);
	for(int i = lst + 1;i < n;i++){
		while(i < (int)v.size() && !Query(v[lst], v[i]))
			i++;
		reverse(v.begin() + lst + 1, v.begin() + i + 1);
		lst = i;
	}	
	for(int i = 0;i < n;i++)
		ret[v[i]] = i;
	return ret;
}

Compilation message (stderr)

monster.cpp:16:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   16 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

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