Submission #419604

#	Time	Username	Problem	Language	Result	Execution time	Memory
419604		Kevin_Zhang_TW	Monster Game (JOI21_monster)	C++17	100 / 100	141 ms	4300 KiB

monster

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "monster.h"


namespace {

const int MAX_N = 1010;

int ans[MAX_N][MAX_N], qcnt;
int qry(int i, int j) { 
	if (!ans[i][j]) {
		++qcnt;
		ans[j][i] = ans[i][j] = Query(i, j) ? i + 10 : j + 10;
	}
	return ans[i][j] - 10;
}

}  // namespace

std::vector<int> Solve(int N) {
	vector<int> sorted(N); iota(AI(sorted), 0);

	{
		int bad_cnt = 0;
		auto cmp = [&](int i, int j) {
			return qry(i, j) == j;
		};
		vector< vector<int> > ids;
		for (int i = 0;i < N;++i) {
			ids.pb();
			ids.back().pb(i);
			while (ids.size() > 1 && end(ids)[-2].size() == end(ids)[-1].size()) {
				vector<int> nid ( end(ids)[-2].size() + end(ids)[-1].size() );
				merge(AI(end(ids)[-2]), AI(end(ids)[-1]), begin(nid), cmp);
				ids.pop_back();
				ids.pop_back();
				ids.pb(nid);
				bad_cnt += nid.size();
			}
		}
		while (ids.size() > 1) {
			vector<int> nid ( end(ids)[-2].size() + end(ids)[-1].size() );
			merge(AI(end(ids)[-2]), AI(end(ids)[-1]), begin(nid), cmp);
			ids.pop_back();
			ids.pop_back();
			ids.pb(nid);
			bad_cnt += nid.size();
		}
		sorted = ids[0];
	}

	auto find_max = [&]() {
		vector<pair<int,int>> cand;

		for (int i : sorted) {
			int lose = 0, sz = 0;
			for (auto [id, cnt] : cand) {
				if (qry(i, id) == i) ++cnt;
				else ++lose;
				if (cnt <= 1)
					cand[sz++] = {id, cnt};
			}
			cand.resize(sz);
			if (lose <= 1) cand.pb(i, lose);
		}

		DE(cand.size());
		assert(cand.size() > 1);
		assert(cand.size() <= 3);
		if (cand.size() == 3) {
			vector<int> big;
			for (auto [id, cnt] : cand) {
				big.pb(id);
			}
			vector<int> lft;
			{
				int x = big[0], y = big[1], z = big[2];
				for (int i = N-4;i >= 0;--i) {
					if (qry(sorted[i], x) != x) {
						lft = {y, z};
						break;
					}
					if (qry(sorted[i], y) != y) {
						lft = {x, z};
						break;
					}
					if (qry(sorted[i], z) != z) {
						lft = {x, y};
						break;
					}
				}
			}

			return lft[0] + lft[1] - qry(lft[0], lft[1]);
		}
		if (cand.size() == 2) {
			int a = cand[0].first, b = cand[1].first;
			return a + b - qry(a, b);
		}
		assert(false);
	};


	auto it = find(AI(sorted), find_max());


	swap(*it, sorted.back() );

	int lst = sorted.back();
	vector<int> stk, rev{lst};
	for (int i = N-2;i >= 0;--i) {
		stk.pb( sorted[i] );
		if (qry( sorted[i], lst ) == sorted[i]) {
			while (stk.size()) {
				rev.pb(stk.back()); stk.pop_back();
			}
			lst = rev.back();
		}
	}

	sorted = rev;
	reverse(AI(sorted));

	vector<int> res(N);
	for (int i = 0;i < N;++i)
		res[ sorted[i] ] = i;

	return res;
}

Compilation message (stderr)

monster.cpp: In lambda function:
monster.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
monster.cpp:82:3: note: in expansion of macro 'DE'
   82 |   DE(cand.size());
      |   ^~

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