Submission #544809

#	Time	Username	Problem	Language	Result	Execution time	Memory
544809		skittles1412	The Collection Game (BOI21_swaps)	C++17	100 / 100	7 ms	532 KiB

swaps

#include "bits/extc++.h"
#include "swaps.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 512, logn = 9;

namespace wrapper {

int perm[maxn];
vector<pair<int, int>> queued;

void init() {
	iota(begin(perm), end(perm), 1);
}

void mschedule(int a, int b) {
	queued.emplace_back(a, b);
}

void mvisit() {
	if (!sz(queued)) {
		return;
	}
	for (auto& [a, b] : queued) {
		schedule(perm[a], perm[b]);
	}
	vector<int> res = visit();
	int rind = 0;
	for (auto& [a, b] : queued) {
		if (!res[rind++]) {
			swap(perm[a], perm[b]);
		}
	}
	queued.clear();
}

void manswer(int n) {
	answer(vector<int>(perm, perm + n));
}

}  // namespace wrapper

int gind;
vector<pair<int, int>> swaps[logn][logn];

void merge(const vector<int>& arr, int d) {
	if (sz(arr) == 2) {
		swaps[gind][d].emplace_back(arr[0], arr[1]);
		return;
	}
	vector<int> nxt[2];
	for (int i = 0; i < sz(arr); i++) {
		nxt[i & 1].push_back(arr[i]);
	}
	merge(nxt[0], d + 1);
	merge(nxt[1], d + 1);
	for (int i = 1; i + 2 < sz(arr); i += 2) {
		swaps[gind][d].emplace_back(arr[i], arr[i + 1]);
	}
}

void solve(int n, int) {
	wrapper::init();
	int tmp[maxn];
	iota(begin(tmp), end(tmp), 0);
	for (int i = 2; i <= maxn; i *= 2) {
		for (int j = 0; j < maxn; j += i) {
			merge(vector<int>(tmp + j, tmp + j + i), 0);
		}
		gind++;
	}
	for (auto& a : swaps) {
		for (int i = logn - 1; i >= 0; i--) {
			if (sz(a[i])) {
				for (auto& [x, y] : a[i]) {
					if (x < n && y < n) {
						wrapper::mschedule(x, y);
					}
				}
				wrapper::mvisit();
			}
		}
	}
	wrapper::manswer(n);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 9 / 9
• Subtask 12: 6 / 6