Submission #534810

#	Time	Username	Problem	Language	Result	Execution time	Memory
534810		skittles1412	The Collection Game (BOI21_swaps)	C++17	50 / 100	483 ms	680 KiB

swaps

#include "swaps.h"
#include "bits/extc++.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 = 505;

namespace s1 {

void sch(int a, int b) {
	schedule(a + 1, b + 1);
}

void answ(vector<int> arr) {
	for (auto& a : arr) {
		a++;
	}
	answer(arr);
	exit(0);
}

bool solve(int n, int m) {
	if (m < 1000) {
		return false;
	}
	bool arr[maxn][maxn] {};
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> vals;
		for (int j = 0; j < n; j++) {
			int x = (n + i - j) % n;
			if (x < j) {
				vals.emplace_back(j, x);
				sch(j, x);
			}
		}
		vector<int> res = visit();
		int rind = 0;
		for (auto& [a, b] : vals) {
			int c = res[rind++];
			arr[a][b] = c;
			arr[b][a] = c ^ 1;
		}
	}
	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int a, int b) -> bool {
		if (a == b) {
			return false;
		}
		return arr[a][b];
	});
	answ(ord);
	return true;
}

}

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 s2 {

bool solve(int n, int m) {
	for (int i = 0; i < m; i += 2) {
		for (int j = 1; j + 1 < n; j += 2) {
			mschedule(j, j + 1);
		}
		mvisit();
		for (int j = 0; j + 1 < n; j += 2) {
			mschedule(j, j + 1);
		}
		mvisit();
	}
	manswer(n);
	return true;
}

}

void solve(int n, int m) {
	init();
	s2::solve(n, m);
}

• 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: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6