Submission #1220605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220605		rainboy	Permutation Game (APIO25_permgame)	C++20	22 / 100	10 ms	332 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], cnt;
char visited[N];

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 || e == m - 1 && k > n - m)
		return k;
	if (e == m - 1) {
		int u = 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;
		}
		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;
			int h = Bob(ii);
			int i = ii[uu[h]], j = ii[vv[h]], tmp;
			tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
		}
		return m == 2 ? n : n - m + 1;
	}
	return -1;
}

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