Submission #873342

#	Time	Username	Problem	Language	Result	Execution time	Memory
873342		rainboy	Shuffle (NOI19_shuffle)	C++17	100 / 100	2 ms	2652 KiB

shuffle

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

using namespace std;

const int N = 1000, L = 11;	/* L = ceil(log2(N)) + 1 */

typedef vector<int> vi;
typedef vector<vi> vvi;

int n, m, k, l;

int pp[L], xx[N], idx[N * N], uu[N], vv[N], cc[N], yy[N], kk[N][N], zz[N];

vvi iii, aaa, aaa_; vi aa;

void shuffle_(vvi iii, vvi &aaa) {
	aaa = shuffle(iii);
	for (int d = 0; d < m; d++)
		for (int g = 0; g < k; g++)
			aaa[d][g]--;
}

void init(int n, int m) {
	l = 1, pp[0] = 1;
	while (pp[l - 1] < n)
		pp[l] = pp[l - 1] * m, l++;
	for (int i = 0; i < n; i++) {
		int x = i + 1 < n ? i : pp[l - 1];
		idx[xx[i] = x] = i;
	}
	if (m == 3 && l == 7)
		l--, idx[xx[k - 1] = 486] = k - 1;
}

void solvep() {
	for (int d = 0; d < n / 2; d++)
		iii[d].clear();
	for (int d = 0; d < n / 2; d++)
		iii[d] = { d * 2 + 1, d * 2 + 2 };
	shuffle_(iii, aaa);
	for (int d = 0; d < n / 2; d++) {
		int a = aaa[d][0], b = aaa[d][1];
		uu[a] = b, uu[b] = a;
	}
	for (int d = 0; d + 1 < n / 2; d++)
		iii[d] = { d * 2 + 2, d * 2 + 3 };
	iii[n / 2 - 1] = { n, 1 };
	shuffle_(iii, aaa);
	for (int d = 0; d < n / 2; d++) {
		int a = aaa[d][0], b = aaa[d][1];
		vv[a] = b, vv[b] = a;
	}
	for (int i = 2, j = n - 1; j - i > 3; i++, j--)
		iii[i - 2] = { i + 1, j + 1 };
	iii[n / 2 - 3] = { n / 2, n / 2 + 2 };
	iii[n / 2 - 2] = { n / 2 + 1, n / 2 + 3 };
	iii[n / 2 - 1] = { 1, 2 };
	shuffle_(iii, aaa);
	int a_ = -1, b_ = -1;
	for (int d = 0; d < n / 2; d++) {
		int a = aaa[d][0], b = aaa[d][1];
		if (uu[a] == b) {
			a_ = a, b_ = b;
			break;
		}
	}
	for (int i = 1, j = n - 2; j - i > 3; i++, j--)
		iii[i - 1] = { i + 1, j + 1 };
	iii[n / 2 - 3] = { n / 2 - 1, n / 2 + 1 };
	iii[n / 2 - 2] = { n / 2, n / 2 + 2 };
	iii[n / 2 - 1] = { n, 1 };
	shuffle_(iii, aaa);
	for (int d = 0; d < n / 2; d++) {
		int a = aaa[d][0], b = aaa[d][1];
		if (vv[a] == b) {
			if (b_ == a || b_ == b)
				a_ = b_;
			break;
		}
	}
	for (int i = 0, a = a_; i < n; i++) {
		aa[i] = a + 1;
		a = i % 2 == 0 ? uu[a] : vv[a];
	}
}

void solvek() {
	for (int d = 0; d < m; d++)
		iii[d].clear();
	for (int i = 0; i < n; i++)
		iii[i / k].push_back(i + 1);
	shuffle_(iii, aaa_);
	for (int c = 0; c < m; c++)
		for (int g = 0; g < k; g++)
			cc[aaa_[c][g]] = c;
	init(k, 2);
	memset(yy, 0, n * sizeof *yy);
	for (int h = 0; h < l; h++) {
		for (int d = 0; d < m; d++)
			iii[d].clear();
		for (int i = 0; i < n; i++)
			iii[(i / k + (xx[i % k] >> h & 1)) % m].push_back(i + 1);
		shuffle_(iii, aaa);
		for (int d = 0; d < m; d++) {
			int u = -1, v = -1, diff = 0;
			for (int g = 0; g < k; g++) {
				int c = cc[aaa[d][g]];
				if (u == -1 || c == u)
					u = c, diff++;
				else
					v = c, diff--;
			}
			if (diff > 0) {
				int tmp;
				tmp = u, u = v, v = tmp;
			}
			if (u != -1)
				vv[u] = v;
			for (int g = 0; g < k; g++) {
				int a = aaa[d][g], c = cc[a];
				if (c == u)
					yy[a] |= 1 << h;
			}
		}
	}
	for (int d = 0; d < m; d++)
		iii[d].clear();
	for (int i = 0; i < k; i++)
		iii[0].push_back(i + 1);
	for (int i = k; i < n; i++)
		iii[i / k].push_back((i - k + 1) % (n - k) + k + 1);
	shuffle_(iii, aaa);
	for (int d = 0; d < m; d++) {
		int c_ = -1;
		for (int g = 0; g < k; g++) {
			int c = cc[aaa[d][g]];
			if (c_ == -1 || c == c_)
				c_ = c;
			else {
				c_ = -1;
				break;
			}
		}
		if (c_ != -1) {
			for (int d = 0, c = c_; d < m; d++, c = vv[c])
				for (int g = 0; g < k; g++) {
					int a = aaa_[c][g];
					aa[d * k + idx[yy[a]]] = a + 1;
				}
			break;
		}
	}
}

void solvem() {
	init(k, m);
	for (int g = k - 1; g >= 0; g--) {
		int x = xx[g];
		for (int d = 0; d < m; d++) {
			int x_ = 0;
			for (int h = 0; h < l; h++)
				x_ += (x / pp[h] + d) % m * pp[h];
			x_ = x_ * m + d;
			idx[xx[g * m + d] = x_] = g * m + d;
		}
	}
	pp[l] = pp[l - 1] * m, l++;
	memset(yy, 0, n * sizeof *yy);
	for (int h = 0; h < l; h++) {
		for (int d = 0; d < m; d++)
			iii[d].clear();
		for (int i = 0; i < n; i++)
			iii[xx[i] / pp[h] % m].push_back(i + 1);
		shuffle_(iii, aaa);
		for (int d = 0; d < m; d++)
			for (int g = 0; g < k; g++)
				yy[aaa[d][g]] += d * pp[h];
	}
	for (int h = 1; h < l; h++) {
		for (int c = 0; c < m; c++)
			memset(kk[c], 0, m * sizeof *kk[c]);
		for (int a = 0; a < n; a++) {
			int c = yy[a] % m, d = yy[a] / pp[h] % m;
			kk[c][d]++;
		}
		for (int c = 0; c < m; c++) {
			int d_ = -1;
			for (int d = 0; d < m; d++)
				if (d_ == -1 || kk[c][d_] < kk[c][d])
					d_ = d;
			cc[d_] = c;
		}
		for (int a = 0; a < n; a++) {
			int d = yy[a] / pp[h] % m;
			yy[a] = yy[a] + (cc[d] - d) * pp[h];
		}
	}
	if (m == 2) {
		for (int d = 0; d < 2; d++)
			iii[d].clear();
		iii[0].push_back(1);
		for (int i = 2; i <= n / 2; i++)
			iii[0].push_back(i + 1);
		iii[1].push_back(2);
		for (int i = n / 2 + 1; i < n; i++)
			iii[1].push_back(i + 1);
		shuffle_(iii, aaa);
		for (int d = 0; d < 2; d++)
			for (int g = 0; g < n / 2; g++)
				if (yy[aaa[d][g]] == 0) {
					int flip = 1;
					for (g = 0; g < n / 2; g++)
						if (yy[aaa[d][g]] == 2) {
							flip = 0;
							break;
						}
					if (flip)
						for (int a = 0; a < n; a++)
							yy[a] ^= (1 << l) - 1;
					goto out;
				}
out:;
	} else {
		for (int a = 0; a < n; a++)
			cc[a] = yy[a] % m;
		memset(zz, 0, m * sizeof *zz);
		for (int h = 0; 1 << h < m; h++) {
			for (int d = 0; d < m; d++)
				iii[d].clear();
			for (int i = 0; i < n; i++)
				iii[i % m].push_back(i + 1);
			for (int c = 0, c_ = -1; c < m; c++)
				if ((c & 1 << h) == 0) {
					if (c_ != -1) {
						int tmp;
						tmp = iii[c][0], iii[c][0] = iii[c_][0], iii[c_][0] = tmp;
					}
					c_ = c;
				}
			shuffle_(iii, aaa);
			for (int d = 0; d < m; d++) {
				int c_ = -1;
				for (int g = 0; g < k; g++) {
					int c = cc[aaa[d][g]];
					if (c_ == -1 || c == c_)
						c_ = c;
					else {
						c_ = -1;
						break;
					}
				}
				if (c_ != -1)
					zz[c_] |= 1 << h;
			}
		}
		for (int a = 0; a < n; a++) {
			int y = 0;
			for (int h = 0; h < l; h++)
				y += zz[yy[a] / pp[h] % m] * pp[h];
			yy[a] = y;
		}
	}
	for (int a = 0; a < n; a++)
		aa[idx[yy[a]]] = a + 1;
}

vi solve(int n_, int m_, int k_, int q, int s) {
	n = n_, m = m_, k = k_;
	iii.resize(m), aa.resize(n);
	if (k == 2)
		solvep();
	else if (k <= 64 && m != 2)
		solvek();
	else
		solvem();
	return aa;
}

• Subtask 1: 2 / 2
• Subtask 2: 3 / 3
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 15 / 15
• Subtask 6: 52 / 52