Submission #800137

#	Time	Username	Problem	Language	Result	Execution time	Memory
800137		ymm	Monster Game (JOI21_monster)	C++17	100 / 100	85 ms	1256 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

namespace {

const int N = 1024;
map<pii,int> mp;

bool cmp(int i, int j)
{
	assert(i != j);
	if (i < j) {
		int &x = mp[pii(i, j)];
		if (!x)
			x = !Query(i, j)+1;
		return x-1;
	} else {
		swap(i, j);
		int &x = mp[pii(i, j)];
		if (!x)
			x = !Query(i, j)+1;
		return 2-x;
	}
}

vector<int> merge(vector<int> a, vector<int> b) {
	vector<int> ans;
	int p0 = 0, p1 = 0;
	while (p0 < a.size() || p1 < b.size()) {
		if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
			ans.push_back(a[p0++]);
		else
			ans.push_back(b[p1++]);
	}
	return ans;
}

vector<int> chain[N];
struct chain_cmp {
	bool operator()(const vector<int> *a, const vector<int> *b) const { 
		return a->size() > b->size();
	}
};

vector<int> get_chain(int n)
{
	priority_queue<vector<int> *, vector<vector<int> *>, chain_cmp> pq;
	Loop (i,0,n) {
		chain[i] = {i};
		pq.push(chain+i);
	}
	while (pq.size() > 1) {
		auto a = pq.top(); pq.pop();
		auto b = pq.top(); pq.pop();
		*a = merge(*a, *b);
		pq.push(a);
	}
	return *pq.top();
}

vector<int> mysolve(vector<int> vec)
{
	if (vec.size() == 1)
		return vec;
	if (vec.size() == 2)
		return {vec[1], vec[0]};
	assert(vec.size() != 3);
	int n = vec.size();
	vector<int> ans;
	int p0 = 0, p1 = 0;
	if (cmp(vec[0], vec[2]) && cmp(vec[1], vec[3])) {
		ans.push_back(vec[1]);
		ans.push_back(vec[0]);
		p0 = p1 = 2;
	} else if (cmp(vec[0], vec[2]) && !cmp(vec[1], vec[3])) {
		ans.push_back(vec[0]);
		p0 = p1 = 1;
	} else if (cmp(vec[3], vec[1]) && cmp(vec[3], vec[0])) {
		p0 = 0, p1 = 3;
		while (p1 < n-1) {
			if (!cmp(vec[p1+1], vec[1]))
				break;
			++p1;
		}
		LoopR (i,0,p1+1)
			ans.push_back(vec[i]);
		p0 = p1 = p1+1;
	} else {
		if (vec.size() != 6) {
			auto tmp = mysolve(vector<int>(vec.begin()+3, vec.end()));
			if (!cmp(vec[0], tmp[0]))
				ans = {vec[2], vec[1], vec[0]};
			else if (!cmp(vec[1], tmp[0]))
				ans = {vec[0], vec[2], vec[1]};
			else
				ans = {vec[1], vec[0], vec[2]};
			ans.insert(ans.end(), tmp.begin(), tmp.end());
			return ans;
		}
		int lst = -1, fst = -1;
		Loop (i,0,3) Loop (j,3,6) {
			if (!cmp(vec[i], vec[j])) {
				lst = vec[i];
				fst = vec[j];
				break;
			}
		}
		vector<int> v1, v2;
		v1 = {vec[2], vec[1], vec[0]};
		v2 = {vec[5], vec[4], vec[3]};
		while (v1.back() != lst) {
			int x = v1.back();
			v1.pop_back();
			v1.insert(v1.begin(), x);
		}
		while (v2.front() != fst) {
			int x = v2.back();
			v2.pop_back();
			v2.insert(v2.begin(), x);
		}
		ans = v1;
		ans.insert(ans.end(), v2.begin(), v2.end());
		return ans;
	}
	while (p0 < n) {
		while (p1 < n-1) {
			if (!cmp(ans.back(), vec[p1]))
				break;
			++p1;
		}
		LoopR (i,p0,p1+1)
			ans.push_back(vec[i]);
		p0 = p1 = p1+1;
	}
	return ans;
}

}  // namespace

std::vector<int> Solve(int n) {
	mp.clear();
	vector<int> vec = get_chain(n);
	vector<int> ans = mysolve(vec);
	vector<int> fans(n);
	Loop (i,0,n)
		fans[ans[i]] = i;
	return fans;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> {anonymous}::merge(std::vector<int>, std::vector<int>)':
monster.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while (p0 < a.size() || p1 < b.size()) {
      |         ~~~^~~~~~~~~~
monster.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while (p0 < a.size() || p1 < b.size()) {
      |                          ~~~^~~~~~~~~~
monster.cpp:35:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
      |       ~~~^~~~~~~~~~~
monster.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
      |                          ~~~^~~~~~~~~~~
monster.cpp: In function 'std::vector<int> {anonymous}::get_chain(int)':
monster.cpp:54:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   54 |   chain[i] = {i};
      |               ^
monster.cpp:54:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]

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