Submission #466033

#	Time	Username	Problem	Language	Result	Execution time	Memory
466033		nonsensenonsense1	Monster Game (JOI21_monster)	C++17	100 / 100	124 ms	320 KiB

monster

#include "monster.h"
#include <vector>
#include <cstring>
#include <numeric>

const int N = 1000;
int a[N], aux[N], less[N];

void run(int l, int r) 
{
	if (r - l <= 1) return;
	int m = l + r >> 1;
	run(l, m);
	run(m, r);
	for (int i = 0, j = 0; i + j < r - l;) {
		if (l + i < m && (m + j == r || Query(a[m + j], a[l + i]))) {
			aux[i + j] = a[l + i];
			++i;
		}
		else {
			aux[i + j] = a[m + j];
			++j;
		}
	}
	memcpy(a + l, aux, r - l << 2);
}

std::vector<int> Solve(int n) 
{
	std::iota(a, a + n, 0);
	run(0, n);
	int k = std::min(n, 12);
	for (int i = 0; i < k; ++i) for (int j = i + 1; j < k; ++j) {
		if (Query(a[i], a[j])) ++less[i];
		else ++less[j];
	}
	int z = -1;
	for (int i = 0; i < k; ++i) if (less[i] == 1) if (z == -1 || Query(a[i], a[z])) z = i;
	int prev = 0;
	std::vector<int> ans(n);
	while (prev < n) {
		for (int i = z; i >= prev; --i) ans[a[i]] = prev + z - i;
		int z_ = z;
		if (z + 1 < n) for (++z; !Query(a[prev], a[z]); ++z);
		prev = z_ + 1;
	}
	return ans;
}

Compilation message (stderr)

monster.cpp: In function 'void run(int, int)':
monster.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int m = l + r >> 1;
      |          ~~^~~
monster.cpp:25:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |  memcpy(a + l, aux, r - l << 2);
      |                     ~~^~~

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