Submission #528763

#	Time	Username	Problem	Language	Result	Execution time	Memory
528763		c28dnv9q3	Monster Game (JOI21_monster)	C++17	100 / 100	134 ms	980 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
namespace {

	bool example_variable;
	vector<int> ans, p;
	map<pi, int> mp;
	bool cmp(int x, int y){
		if(mp.find(pi(x, y)) != mp.end()) return mp[pi(x, y)];
		return mp[pi(x, y)] = !Query(x, y);
	}
}  // namespace


void solve(int l, int r){
	if(l == r) return;
	int m = (l + r) / 2;
	solve(l, m); solve(m + 1, r);
	int p1 = l, p2 = m + 1;
	vector<int> dap;
	while(p1 < m+1 && p2 < r+1){
		if(cmp(p[p1], p[p2])){
			dap.push_back(p[p1++]);
		}
		else dap.push_back(p[p2++]);
	}
	while(p1 < m+1) dap.push_back(p[p1++]);
	while(p2 < r+1) dap.push_back(p[p2++]);
	for(int i=l; i<=r; i++) p[i] = dap[i - l];
}

std::vector<int> Solve(int N) {
	p.resize(N);
	iota(all(p), 0);
	solve(0, N - 1);
	vector<vector<int>> cycles;
	for(int i = 0; i < N; ){
		vector<int> cur_stack;
		int e = i;
		while(e < N && e < i + 3){
			cur_stack.push_back(p[e++]);
		}
		while(e < N && !(cmp(p[e - 1], cur_stack[0]) && !cmp(p[e], cur_stack[0]))){
			cur_stack.push_back(p[e++]);
		}
		cycles.push_back(cur_stack);
		i = e;
	}
	bool normal = 0;
	for(int i = 0; i < sz(cycles); i++){
		if(sz(cycles[i]) >= 4){
			vector<int> v;
			for(int j = 0; j < sz(cycles[i]); j++){
				if(cmp(cycles[i][j], cycles[i][(j+2)%sz(cycles[i])])){
					v.push_back(j);
				}
			}
			assert(sz(v) == 2);
			if(v[1] - v[0] != 1) swap(v[0], v[1]);
			rotate(cycles[i].begin(), cycles[i].begin() + v[1] + 1, cycles[i].end());
			int idx = i;
			{
				for(int i = idx + 1; i < sz(cycles); i++){
					for(int j = 0; j < sz(cycles[i]); j++){
						if(!cmp(cycles[i-1][0], cycles[i][j])){
							rotate(cycles[i].begin(), cycles[i].begin() + j + 1, cycles[i].end());
							break;
						}
					}
				}
				for(int i = idx - 1; i >= 0; i--){
					for(int j = 0; j < sz(cycles[i]); j++){
						if(!cmp(cycles[i][j], cycles[i + 1].back())){
							rotate(cycles[i].begin(), cycles[i].begin() + j, cycles[i].end());
							break;
						}
					}
				}
			}
			normal = 1;
			break;
		}
	}
	if(!normal){
		for(int i = 0; i < sz(cycles[0]); i++){
			for(int j = 0; j < sz(cycles[1]); j++){
				if(!cmp(cycles[0][i], cycles[1][j])){
					rotate(cycles[0].begin(), cycles[0].begin() + i, cycles[0].end());
					rotate(cycles[1].begin(), cycles[1].begin() + j + 1, cycles[1].end());
					break;
				}
			}
		}
		for(int i = 2; i < sz(cycles); i++){
			for(int j = 0; j < sz(cycles[i]); j++){
				if(!cmp(cycles[i-1][0], cycles[i][j])){
					rotate(cycles[i].begin(), cycles[i].begin() + j + 1, cycles[i].end());
					break;
				}
			}
		}
	}
	vector<int> ans;
	for(auto &i : cycles){
		reverse(all(i));
		for(auto &j : i) ans.push_back(j);
	}
	{
		vector<int> S(N);
		for(int i = 0; i < N; i++) S[ans[i]] = i;
		return S;
	}
}

Compilation message (stderr)

monster.cpp: In function 'bool {anonymous}::cmp(int, int)':
monster.cpp:15:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   15 |   return mp[pi(x, y)] = !Query(x, y);
monster.cpp: At global scope:
monster.cpp:10:7: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   10 |  bool example_variable;
      |       ^~~~~~~~~~~~~~~~

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