Submission #1224719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224719		rainboy	Permutation Game (APIO25_permgame)	C++20	100 / 100	15 ms	332 KiB

permgame

/* https://codeforces.com/blog/entry/142848?#comment-1276236 (errorgorn) */
#include "permgame.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 400, M = N;

int min(int a, int b) { return a < b ? a : b; }

int uu[M], vv[M], ev[M][2], eo[M], ww[M], m;
int pp[N], rr[N], cc[N], ii[N], jj[N], n, k;

int score() {
	int s = 0;
	for (int i = 0; i < n; i++)
		if (pp[i] == i)
			s++;
	return s;
}

char visited[N]; int kk[N + 1], rr_[N];

void decompose() {
	memset(visited, 0, n * sizeof *visited), memset(kk, 0, (n + 1) * sizeof *kk);
	k = 0;
	for (int r = 0; r < n; r++)
		if (!visited[r]) {
			int c = 0;
			while (!visited[r])
				c++, visited[r] = 1, r = pp[r];
			cc[r] = c, rr_[k++] = r;
			kk[c - 1]++;
		}
	for (int c = n - 1; c >= 0; c--)
		kk[c] += kk[c + 1];
	for (int h = 0; h < k; h++) {
		int r = rr_[h], c = cc[r];
		rr[kk[c]++] = r;
	}
}

void get_cycle(int *ii, int r) {
	int i = r, cnt = 0;
	do
		ii[cnt++] = i;
	while ((i = pp[i]) != r);
}

vi ii_;

void move() {
	for (int h = 0; h < m; h++)
		ii_[ww[h]] = ii[h];
	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_) {
	n = n_, m = m_;
	for (int h = 0; h < m; h++)
		uu[h] = uu_[h], vv[h] = vv_[h];
	for (int i = 0; i < n; i++)
		pp[i] = pp_[i];
	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 s_ = score();
	if (bad || s_ >= n - m + 1)
		return s_;
	if (e == m - 1) {
		int u = 0;
		while (eo[u] > 1)
			u++;
		int v = ev[u][0];
		int cnt = 0;
		ww[cnt++] = u;
		while (eo[v] > 1) {
			ww[cnt++] = v;
			int w = u ^ ev[v][0] ^ ev[v][1];
			u = v, v = w;
		}
		ww[cnt++] = v;
		s_ = m == 2 ? n : n - m + 1;
	} else {
		int u = 0, v = ev[u][0];
		int cnt = 0;
		ww[cnt++] = u;
		while (v != u) {
			ww[cnt++] = v;
			int w = u ^ ev[v][0] ^ ev[v][1];
			u = v, v = w;
		}
		if (m % 2 == 0)
			s_ = s_ == n - m ? n - m + 1 : n - m - 1;
		else {
			decompose();
			int c = 0, k1 = 0, l1 = 0;
			for (int h = 0; h < k; h++) {
				int r = rr[h];
				if (cc[r] % 2 == 0)
					c += cc[r];
				else
					k1++;
			}
			for (int h = 0; h < k && c < m; h++) {
				int r = rr[h];
				if (cc[r] % 2 != 0)
					c += cc[r], l1++;
			}
			s_ = k1 - l1 / 2 * 2;
		}
	}
	ii_.resize(m);
	int s;
	while ((s = score()) < s_) {
		decompose();
		if (e == m - 1 || s == n - m) {
			int cnt = 0;
			for (int h = 0; h < k; h++) {
				int r = rr[h];
				get_cycle(ii + cnt, r), cnt += cc[r];
			}
		} else if (m % 2 != 0) {
			int r_ = -1;
			for (int h = 0; h < k; h++) {
				int r = rr[h];
				if (cc[r] % 2 != 0) {
					r_ = r;
					break;
				}
			}
			if (cc[r_] == m)
				get_cycle(ii, r_);
			else if (cc[r_] > m) {
				get_cycle(jj, r_);
				int cnt = 0;
				for (int h = 0; h < m; h += 2)
					ii[cnt++] = jj[h];
				for (int h = m - 2; h >= 1; h -= 2)
					ii[cnt++] = jj[h];
			} else {
				get_cycle(ii, r_);
				int cnt = cc[r_];
				for (int h = 0; h < k; h++) {
					int r = rr[h];
					if (cc[r] % 2 == 0)
						get_cycle(ii + cnt, r), cnt += cc[r];
				}
				for (int h = 0; h < k; h++) {
					int r = rr[h];
					if (cc[r] % 2 != 0 && r != r_)
						get_cycle(ii + cnt, r), cnt += cc[r];
				}
			}
		} else {
			int r_ = -1;
			for (int h = 0; h < k; h++) {
				int r = rr[h];
				if (cc[r] == m) {
					r_ = r;
					break;
				}
			}
			if (r_ != -1)
				get_cycle(ii, r_);
			else if (cc[rr[0]] >= m * 2 || k == 1 || cc[rr[1]] == 1) {
				get_cycle(jj, rr[0]);
				int d = cc[rr[0]] - m, md = (d - 1) * 2;
				int cnt = 0, h = 0;
				ii[cnt++] = jj[0];
				while (cnt < m / 2) {
					h += h % md == 0 ? d : 1;
					ii[cnt++] = jj[h];
				}
				h++;
				ii[cnt++] = jj[h];
				h -= d;
				ii[cnt++] = jj[h];
				while (cnt < m) {
					h -= h % md == 1 ? d : 1;
					ii[cnt++] = jj[h];
				}
			} else {
				get_cycle(ii, rr[0]);
				int cnt = min(cc[rr[0]], m - 1);
				for (int h = 1; h < k; h++) {
					int r = rr[h];
					get_cycle(ii + cnt, r), cnt += cc[r];
				}
			}
		}
		move();
	}
	return s_;
}

• 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