Submission #1208666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208666		k1r1t0	Permutation Game (APIO25_permgame)	C++20	100 / 100	18 ms	532 KiB

permgame

#include <bits/stdc++.h>

using namespace std;

int Bob(vector<int> t);

const int NN = 410;

int MM;
vector<int> g[NN], ord, Uu, Vv;
bool used[NN];

int count_ones;
vector<vector<int>> cycles(const vector<int> &p) {
	int n = (int) p.size();
	vector<bool> used(n, false);
	vector<vector<int>> res;
	count_ones = 0;
	for (int i = 0; i < n; i++) {
		if (used[i]) continue;
		int t = i;
		vector<int> cur;
		do {
			cur.push_back(t);
			used[t] = true;
			t = p[t];
		} while (t != i);
		if (cur.size() == 1)
			count_ones++;
		if (cur.size() != 1)
			res.push_back(cur);
	}
	return res;
}

void dfs(int v) {
	if (used[v]) return;
	used[v] = true;
	ord.push_back(v);
	for (int u : g[v])
		dfs(u);
}

void upd(vector<int> t, vector<int> &p) {
	vector<int> val(MM);
	for (int i = 0; i < MM; i++) val[ord[i]] = t[i];
	int edge = Bob(val);
	swap(p[val[Uu[edge]]], p[val[Vv[edge]]]);
}

void split(vector<int> t, vector<int> &p) {
	vector<int> cur;
	int k = (int) t.size() - MM;
	cur.push_back(0);
	for (int i = 0; i < MM / 2 - 1; i++)
		if (cur.back() % (2 * k - 2) == 0)
			cur.push_back(cur.back() + k);
		else
			cur.push_back(cur.back() + 1);
	cur.push_back(cur.back() + 1);
	cur.push_back(cur.back() - k);
	for (int i = 0; i < MM / 2 - 2; i++)
		if (cur.back() % (2 * k - 2) == 1)
			cur.push_back(cur.back() - k);
		else
			cur.push_back(cur.back() - 1);
	for (int i = 0; i < MM; i++)
		cur[i] = t[cur[i]];
	upd(cur, p);
}

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
	MM = m;
	Uu = u;
	Vv = v;
	if (m == 2) {
		for (int i = 0; i < n; i++) {
			int pos = -1;
			for (int j = 0; j < n; j++)
				if (p[j] == i) pos = j;
			if (pos == i) continue;
			Bob({i, pos});
			swap(p[i], p[pos]);
		}
		return n;
	}
	int orig = 0;
	for (int i = 0; i < n; i++)
		if (p[i] == i)
			orig++;
	if (orig >= n - m + 1) return orig;
	for (int i = 0; i < e; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	int maxdeg = 0, mindeg = 2;
	for (int i = 0; i < m; i++) {
		maxdeg = max(maxdeg, (int) g[i].size());
		mindeg = min(mindeg, (int) g[i].size());
	}
	if (maxdeg >= 3) return orig;
	for (int i = 0; i < m; i++)
		if ((int) g[i].size() == mindeg) {
			dfs(i);
			break;
		}
	if (mindeg <= 1 || (m % 2 == 0 && orig == n - m)) {
		while (orig < n - m + 1) {
			auto st = cycles(p);
			vector<int> cur;
			for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
			for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
				cur.push_back(st[i][j]);
			upd(cur, p);
			orig = 0;
			for (int i = 0; i < n; i++)
				if (p[i] == i)
					orig++;
		}
		return n - m + 1;
	}
	if (m % 2 == 1) {
		auto st = cycles(p);
		int opt = count_ones, sum = 0, k = 0;
		for (int i = 0; i < (int) st.size(); i++)
			if (st[i].size() % 2 == 1) opt++;
			else sum += st[i].size();
		sort(begin(st), end(st), [&](auto x, auto y) {
			return x.size() > y.size();
		});
		for (int i = 0; i < (int) st.size() && sum < m; i++)
			if ((int) st[i].size() % 2 == 1) {
				k++;
				sum += (int) st[i].size();
			}
		opt -= 2 * (k / 2);
		while (orig < opt) {
			vector<int> cur;
			for (int i = 0; i < (int) st.size(); i++) {
				if ((int) st[i].size() % 2 == 0) continue;
				if ((int) st[i].size() < m) continue;
				if ((int) st[i].size() == m) cur = st[i];
				else {
					for (int j = 0; j < m; j += 2)
						cur.push_back(st[i][j]);
					for (int j = m - 2; j > 0; j -= 2)
						cur.push_back(st[i][j]);
				}
				upd(cur, p);
				goto fin;
			}
			for (int i = 0; i < (int) st.size(); i++)
				if ((int) st[i].size() % 2 == 0)
					for (int j = 0; j < (int) st[i].size(); j++)
						cur.push_back(st[i][j]);
			while ((int) cur.size() > m - 1)
				cur.pop_back();
			for (int i = 0; i < (int) st.size(); i++)
				if ((int) st[i].size() % 2 == 1)
					for (int j = 0; j < (int) st[i].size(); j++)
						cur.push_back(st[i][j]);
			while ((int) cur.size() > m)
				cur.pop_back();
			upd(cur, p);
			fin:;
			orig = 0;
			for (int i = 0; i < n; i++)
				if (p[i] == i)
					orig++;
			st = cycles(p);
		}
		return opt;
	}
	int opt = n - m - 1;
	auto st = cycles(p);
	while (orig < opt) {
		int all = 0;
		vector<int> cur;
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() == m) {
				upd(st[i], p);
				goto fin1;
			}
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() >= m + 2) {
				split(st[i], p);
				goto fin1;
			}
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() > 2)
				all += (int) st[i].size();
		if (all < m + 2)
			break;
		sort(begin(st), end(st), [&](auto x, auto y) {
			return x.size() < y.size();
		});
		for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
			if (st[i].size() > 2)
				for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
					cur.push_back(st[i][j]);
		upd(cur, p);
		fin1:;
		orig = 0;
		for (int i = 0; i < n; i++)
			if (p[i] == i)
				orig++;
		st = cycles(p);
	}
	orig = 0;
	for (int i = 0; i < n; i++)
		if (p[i] == i)
			orig++;
	st = cycles(p);
	while (orig < opt) {
		vector<int> cur;
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() == m) {
				upd(st[i], p);
				goto fin2;
			}
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() >= 2 * m - 1) {
				split(st[i], p);
				goto fin2;
			}
		if ((int) st.size() == 1)
			break;
		sort(begin(st), end(st), [&](auto x, auto y) {
			return x.size() > y.size();
		});
		for (int i = 0; i < (int) st.size(); i++) {
			for (int j = 0; j < (int) st[i].size(); j++)
				cur.push_back(st[i][j]);
			if (cur.size() >= m && st[i].size() == cur.size()) {
				while (cur.size() >= m)
					cur.pop_back();
			}
		}
		upd(cur, p);
		fin2:;
		orig = 0;
		for (int i = 0; i < n; i++)
			if (p[i] == i)
				orig++;
		st = cycles(p);
	}
	orig = 0;
	for (int i = 0; i < n; i++)
		if (p[i] == i)
			orig++;
	st = cycles(p);
	while (orig < opt) {
		vector<int> cur;
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() == m) {
				upd(st[i], p);
				goto fin3;
			}
		for (int i = 0; i < (int) st.size(); i++)
			if ((int) st[i].size() >= m + 2) {
				split(st[i], p);
				goto fin3;
			}
		sort(begin(st), end(st), [&](auto x, auto y) {
			return x.size() < y.size();
		});
		for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
			for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
				cur.push_back(st[i][j]);
		upd(cur, p);
		fin3:;
		orig = 0;
		for (int i = 0; i < n; i++)
			if (p[i] == i)
				orig++;
		st = cycles(p);
	}
	return opt;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24
• Subtask 6: 30 / 30