Submission #1220756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220756		rainboy	Permutation Game (APIO25_permgame)	C++20	70 / 100	9 ms	328 KiB

permgame

#include "permgame.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 400;

int ev[N][2], eo[N], ww[N], qu[N];
char visited[N];

void move(vi uu, vi vv, vi &pp, vi ii) {
	int h = Bob(ii);
	int i = ii[uu[h]], j = ii[vv[h]], tmp;
	tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
}

int Alice(int m, int e, vi uu, vi vv, int n, vi pp) {
	memset(eo, 0, m * sizeof *eo);
	int bad = 0;
	for (int h = 0; h < e; h++) {
		int u = uu[h], v = vv[h];
		if (eo[u] == 2 || eo[v] == 2) {
			bad = 1;
			break;
		}
		ev[u][eo[u]++] = v, ev[v][eo[v]++] = u;
	}
	int k = 0;
	for (int i = 0; i < n; i++)
		if (pp[i] == i)
			k++;
	if (bad)
		return k;
	if (e == m - 1) {
		int u = 0, cnt = 0;
		while (eo[u] == 2)
			u++;
		ww[cnt++] = u;
		int v = ev[u][0];
		while (1) {
			ww[cnt++] = v;
			if (eo[v] == 1)
				break;
			int w = u ^ ev[v][0] ^ ev[v][1];
			u = v, v = w;
		}
	} else {
		int u = 0, v = ev[u][0], cnt = 0;
		ww[cnt++] = u;
		while (1) {
			ww[cnt++] = v;
			int w = u ^ ev[v][0] ^ ev[v][1];
			if (w == 0)
				break;
			u = v, v = w;
		}
	}
	if (e == m - 1) {
		if (k > n - m)
			return k;
		vi ii(m);
		while (1) {
			memset(visited, 0, n * sizeof *visited);
			int k = 0;
			for (int i = 0; i < n && k < m; i++)
				if (pp[i] != i && !visited[i])
					while (!visited[i] && k < m)
						ii[ww[k++]] = i, visited[i] = 1, i = pp[i];
			if (k < m)
				break;
			move(uu, vv, pp, ii);
		}
		return m == 2 ? n : n - m + 1;
	} else if (m == 3) {
		memset(visited, 0, n * sizeof *visited);
		int k = 0;
		for (int i = 0; i < n; i++)
			if (!visited[i]) {
				int c = 0;
				while (!visited[i])
					c++, visited[i] = 1, i = pp[i];
				if (c % 2 != 0)
					k++;
			}
		vi ii(m);
		while (1) {
			memset(visited, 0, n * sizeof *visited);
			int moved = 0;
			for (int i = 0; i < n; i++)
				if (pp[i] != i && !visited[i]) {
					int c = 0;
					while (!visited[i])
						c++, visited[i] = 1, i = pp[i];
					if (c % 2 != 0) {
						ii[ww[0]] = i, ii[ww[1]] = pp[i], ii[ww[2]] = pp[pp[i]];
						move(uu, vv, pp, ii);
						moved = 1;
						break;
					}
				}
			if (!moved)
				break;
		}
		return k;
	} else if (m == 4) {
		int ans = k > n - m ? k : (k == n - m ? n - m + 1 : n - m - 1);
		vi ii(m);
		while (1) {
			int k = 0;
			for (int i = 0; i < n; i++)
				if (pp[i] != i)
					k++;
			if (k < m)
				break;
			if (k == m) {
				memset(visited, 0, n * sizeof *visited);
				k = 0;
				for (int i = 0; i < n; i++)
					if (pp[i] != i && !visited[i])
						while (!visited[i])
							ii[ww[k++]] = i, visited[i] = 1, i = pp[i];
				move(uu, vv, pp, ii);
				continue;
			}
			if (k == m + 1)
				break;
			memset(visited, 0, n * sizeof *visited);
			int moved = 0;
			for (int i = 0; i < n; i++)
				if (pp[i] != i && !visited[i]) {
					int c = 0;
					while (!visited[i])
						qu[c++] = i, visited[i] = 1, i = pp[i];
					if (c == 4) {
						ii[ww[0]] = qu[0], ii[ww[1]] = qu[1], ii[ww[2]] = qu[2], ii[ww[3]] = qu[3];
						move(uu, vv, pp, ii);
						moved = 1;
						break;
					} else if (c >= 6) {
						ii[ww[0]] = qu[0], ii[ww[1]] = qu[1], ii[ww[2]] = qu[5], ii[ww[3]] = qu[4];
						move(uu, vv, pp, ii);
						moved = 1;
						break;
					}
				}
			if (moved)
				continue;
			memset(visited, 0, n * sizeof *visited);
			k = 0;
			int first = 1;
			for (int i = 0; i < n && k < m; i++)
				if (pp[i] != i && !visited[i]) {
					while (!visited[i] && k < m)
						ii[ww[k++]] = i, visited[i] = 1, i = pp[i];
					if (first && k == m)
						k--;
					first = 0;
				}
			move(uu, vv, pp, ii);
		}
		return ans;
	}
	return -1;
}

• 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: 0 / 30