Submission #800070

#	Time	Username	Problem	Language	Result	Execution time	Memory
800070		ymm	Monster Game (JOI21_monster)	C++17	0 / 100	204 ms	1848 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];
bool chain_cmp(vector<int> *a, vector<int> *b) { return a->size() > b->size(); }

vector<int> get_chain(int n)
{
	priority_queue<vector<int> *> 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();
}

}  // namespace

std::vector<int> Solve(int n) {
	vector<int> vec = get_chain(n);
	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 {
		int cnt = 0;
		vector<int> dard;
		Loop (i,1,n) {
			if (!cmp(vec[0], vec[i]))
				dard.push_back(i);
			if (dard.size() == 2)
				break;
		}
		if (dard.size() == 1) {
			ans.push_back(vec[0]);
			ans.push_back(vec[2]);
			ans.push_back(vec[1]);
			p0 = p1 = 3;
		} else {
			p0 = 0, p1 = 2;
			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;
		}
	}
	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;
	}
	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:50:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   50 |   chain[i] = {i};
      |               ^
monster.cpp:50:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:76:7: warning: unused variable 'cnt' [-Wunused-variable]
   76 |   int cnt = 0;
      |       ^~~
monster.cpp: At global scope:
monster.cpp:44:6: warning: 'bool {anonymous}::chain_cmp(std::vector<int>*, std::vector<int>*)' defined but not used [-Wunused-function]
   44 | bool chain_cmp(vector<int> *a, vector<int> *b) { return a->size() > b->size(); }
      |      ^~~~~~~~~

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