Submission #777255

#	Time	Username	Problem	Language	Result	Execution time	Memory
777255		rainboy	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	657 ms	325796 KiB

abc

/* https://github.com/apio2023/apio2023_tasks/blob/main/abc/en%20-%20Alice%2C%20Bob%20and%20Circuit.pptx */
#include "abc.h"
#include <cstring>
#include <functional>

using namespace std;

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

int alice(const int n, const char ss[][5], const unsigned short ww[], bool aa[]) {
	if (n == 0)
		return 1;
	const int N = 700, LN = 10, N_ = 1 << LN;	// LN = ceil(log2(N))
	const int KX = 19, KY = 16;	// KX = ceil(log2(26^4+26^3+26^2+26^1+26^0))
	int xx[N], n_, ln, la;
	function<int()> rand_ = [&]() {
		static unsigned int Z = 12345;
		return (Z *= 3) >> 1;
	};
	function<void(int *, int, int)> sort = [&](int *ii, int l, int r) {
		while (l < r) {
			int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
			while (j < k)
				if (xx[ii[j]] == xx[i_])
					j++;
				else if (xx[ii[j]] < xx[i_]) {
					tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
					i++, j++;
				} else {
					k--;
					tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
				}
			sort(ii, l, i);
			l = k;
		}
	};
	int vv[N_]; char visited[N_], flip[N_];
	function<void(int *, int)> print_perm = [&](int *ii, int ln) {
		if (ln == 0)
			return;
		int n = 1 << ln, m = n >> 1;
		for (int h = 0; h < n; h++)
			vv[ii[h] & n - 1] = h;
		memset(visited, 0, m * sizeof *visited), memset(flip, 0, m * sizeof *flip);
		for (int h = 0; h < m; h++)
			while (!visited[h]) {
				visited[h] = 1;
				int h_ = vv[ii[h ^ m] & n - 1 ^ m];
				if ((h_ & m) != 0) {
					h_ ^= m;
					int i = ii[h_], j = ii[h_ ^ m];
					ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
					flip[h_] = 1;
				}
				h = h_;
			}
		for (int h = 0; h < m; h++)
			aa[la++] = flip[h];
		print_perm(ii, ln - 1), print_perm(ii + m, ln - 1);
		for (int h = 0; h < m; h++)
			if ((ii[h] & m) == 0)
				aa[la++] = 0;
			else {
				aa[la++] = 1;
				int tmp;
				tmp = ii[h], ii[h] = ii[h ^ m], ii[h ^ m] = tmp;
			}
	};
	for (int i = 0; i < n; i++) {
		int len = strlen(ss[i]);
		xx[i] = 0;
		for (int h = 0; h < len; h++)
			xx[i] = xx[i] * 26 + (ss[i][h] - 'a' + 1);
	}
	ln = 0;
	while (1 << ln < n)
		ln++;
	n_ = 1 << ln;
	int ii[N_];
	for (int i = 0; i < n_; i++)
		ii[i] = i;
	sort(ii, 0, n);
	la = 0;
	for (int h = 0; h < n; h++) {
		int i = ii[h];
		for (int k = 0; k < KX; k++)
			aa[la++] = xx[i] >> k & 1;
		for (int k = 0; k < KX; k++)
			aa[la++] = xx[i] >> k & 1;
		for (int k = 0; k < KY; k++)
			aa[la++] = ww[i] >> k & 1;
		aa[la++] = 0;
	}
	print_perm(ii, ln);
	return la;
}

int bob(const int m, const char ss[][5], const char tt[][5], bool bb[]) {
	if (m == 0)
		return 1;
	const int M = 1000, LM = 10, M_ = 1 << LM;	// LM = ceil(log2(M))
	const int KX = 19, KY = 16;	// KX = ceil(log2(26^4+26^3+26^2+26^1+26^0))
	int xx[M], yy[M], m_, lm, lb;
	function<int()> rand_ = [&]() {
		static unsigned int Z = 12345;
		return (Z *= 3) >> 1;
	};
	int *xx_;
	function<void(int *, int, int)> sort = [&](int *jj, int l, int r) {
		while (l < r) {
			int i = l, j = l, k = r, j_ = jj[l + rand_() % (r - l)], tmp;
			while (j < k)
				if (xx_[jj[j]] == xx_[j_])
					j++;
				else if (xx_[jj[j]] < xx_[j_]) {
					tmp = jj[i], jj[i] = jj[j], jj[j] = tmp;
					i++, j++;
				} else {
					k--;
					tmp = jj[j], jj[j] = jj[k], jj[k] = tmp;
				}
			sort(jj, l, i);
			l = k;
		}
	};
	int vv[M_]; char visited[M_], flip[M_];
	function<void(int *, int)> print_perm = [&](int *ii, int ln) {
		if (ln == 0)
			return;
		int n = 1 << ln, m = n >> 1;
		for (int h = 0; h < n; h++)
			vv[ii[h] & n - 1] = h;
		memset(visited, 0, m * sizeof *visited), memset(flip, 0, m * sizeof *flip);
		for (int h = 0; h < m; h++)
			while (!visited[h]) {
				visited[h] = 1;
				int h_ = vv[ii[h ^ m] & n - 1 ^ m];
				if ((h_ & m) != 0) {
					h_ ^= m;
					int i = ii[h_], j = ii[h_ ^ m];
					ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
					flip[h_] = 1;
				}
				h = h_;
			}
		for (int h = 0; h < m; h++)
			bb[lb++] = flip[h];
		print_perm(ii, ln - 1), print_perm(ii + m, ln - 1);
		for (int h = 0; h < m; h++)
			if ((ii[h] & m) == 0)
				bb[lb++] = 0;
			else {
				bb[lb++] = 1, ii[h] ^= m, ii[h ^ m] ^= m;
				int tmp;
				tmp = ii[h], ii[h] = ii[h ^ m], ii[h ^ m] = tmp;
			}
	};
	for (int j = 0; j < m; j++) {
		int len;
		len = strlen(ss[j]);
		xx[j] = 0;
		for (int h = 0; h < len; h++)
			xx[j] = xx[j] * 26 + (ss[j][h] - 'a' + 1);
		len = strlen(tt[j]);
		yy[j] = 0;
		for (int h = 0; h < len; h++)
			yy[j] = yy[j] * 26 + (tt[j][h] - 'a' + 1);
	}
	lm = 0;
	while (1 << lm < m)
		lm++;
	m_ = 1 << lm;
	int jjx[M_];
	for (int j = 0; j < m_; j++)
		jjx[j] = j;
	xx_ = xx, sort(jjx, 0, m);
	lb = 0;
	for (int h = 0; h < m; h++) {
		int j = jjx[h];
		for (int k = 0; k < KX; k++)
			bb[lb++] = xx[j] >> k & 1;
		for (int k = 0; k < KX; k++)
			bb[lb++] = yy[j] >> k & 1;
		for (int k = 0; k < KY; k++)
			bb[lb++] = 0 >> k & 1;
		bb[lb++] = 1;
	}
	int jjy[M];
	for (int j = 0; j < m; j++)
		jjy[j] = j;
	xx_ = yy, sort(jjy, 0, m);
	for (int j = 0; j < m; j++)
		vv[jjy[j]] = j;
	for (int j = 0; j < m; j++)
		jjx[j] = vv[jjx[j]];
	print_perm(jjx, lm);
	return lb;
}

int circuit(const int la, const int lb, int tt[], int uv[][2], int cc[][16]) {
	const int N = 700, LN = 10, N_ = 1 << LN;	// LN = ceil(log2(N))
	const int M = 1000;	// LM = ceil(log2(M))
	const int KX = 19, KY = 16, K = KX * 2 + KY + 1;	// KX = ceil(log2(26^4+26^3+26^2+26^1+26^0))
	int lc = la + lb;
	function<int(int, int, int)> gate = [&](int t, int u, int v) {
		tt[lc] = t, uv[lc][0] = u, uv[lc][1] = v;
		return lc++;
	};
	int ZERO = gate(OP_ZERO, 0, 0), ONE = gate(OP_ONE, 0, 0);
	function<void(int *, int *, int)> swap = [&](int *uu, int *vv, int z) {
		for (int k = 0; k < K; k++) {
			int x = gate(OP_AND, gate(OP_XOR, uu[k], vv[k]), z);
			uu[k] = gate(OP_XOR, uu[k], x);
			vv[k] = gate(OP_XOR, vv[k], x);
		}
	};
	function<void(int *, int *, int)> set = [&](int *uu, int *vv, int z) {
		for (int k = KX * 2; k < KX * 2 + KY; k++) {
			int x = gate(OP_AND, gate(OP_XOR, uu[k], vv[k]), z);
			uu[k] = gate(OP_XOR, uu[k], x);
		}
	};
	function<void(int *, int)> clear = [&](int *uu, int z) {
		for (int k = KX * 2; k < KX * 2 + KY; k++) {
			int x = gate(OP_AND, uu[k], z);
			uu[k] = gate(OP_XOR, uu[k], x);
		}
	};
	function<void(int *, int *, int)> add = [&](int *uu, int *vv, int z) {
		int c = ZERO;
		for (int k = KX * 2; k < KX * 2 + KY; k++) {
			int c_ = gate(OP_OR, gate(OP_OR, gate(OP_AND, uu[k], vv[k]), gate(OP_AND, vv[k], c)), gate(OP_AND, c, uu[k]));
			uu[k] = gate(OP_XOR, uu[k], gate(OP_AND, gate(OP_XOR, vv[k], c), z));
			c = c_;
		}
	};
	int zz[(N + M) * (LN + 1)], cnt = 0, mode;
	function<void(int *, int *)> cmp_swap = [&](int *uu, int *vv) {
		int z;
		if (mode == 0) {
			z = gate(OP_GREATER, uu[K - 1], vv[K - 1]);
			for (int k = 0; k < KX; k++) {
				z = gate(OP_OR, z, gate(OP_GREATER, uu[k], vv[k]));
				z = gate(OP_AND, z, gate(OP_GEQ, uu[k], vv[k]));
			}
		} else {
			z = gate(OP_LESS, uu[K - 1], vv[K - 1]);
			for (int k = KX; k < KX * 2; k++) {
				z = gate(OP_OR, z, gate(OP_GREATER, uu[k], vv[k]));
				z = gate(OP_AND, z, gate(OP_GEQ, uu[k], vv[k]));
			}
		}
		zz[cnt++] = z, swap(uu, vv, z);
	};
	function<void(int *, int *)> cmp_unswap = [&](int *uu, int *vv) {
		int z = zz[--cnt];
		swap(uu, vv, z);
	};
	int idx;
	function<void(int *, int)> apply_perm = [&](int *uu, int ln) {
		if (ln == 0)
			return;
		int n = 1 << ln, m = n >> 1;
		for (int h = 0; h < m; h++)
			swap(uu + h * K, uu + (h ^ m) * K, idx++);
		apply_perm(uu, ln - 1), apply_perm(uu + m * K, ln - 1);
		for (int h = 0; h < m; h++)
			swap(uu + h * K, uu + (h ^ m) * K, idx++);
	};
	function<void(int *, int)> semisort = [&](int *uu, int n) {
		if (n <= 1)
			return;
		int l = 0;
		while (1 << l + 1 < n)
			l++;
		for (int i = 0; i < n - (1 << l); i++)
			cmp_swap(uu + i * K, uu + (i + (1 << l)) * K);
		semisort(uu, n - (1 << l)), semisort(uu + (n - (1 << l)) * K, 1 << l);
	};
	function<void(int *, int)> unsemisort = [&](int *uu, int n) {
		if (n <= 1)
			return;
		int l = 0;
		while (1 << l + 1 < n)
			l++;
		unsemisort(uu + (n - (1 << l)) * K, 1 << l), unsemisort(uu, n - (1 << l));
		for (int i = n - (1 << l) - 1; i >= 0; i--)
			cmp_unswap(uu + i * K, uu + (i + (1 << l)) * K);
	};
	int n = 0, ln = 0;
	if (la > 1)
		while (n * K + (1 << ln) * ln < la) {
			n++;
			if (1 << ln < n)
				ln++;
		}
	int n_ = 1 << ln;
	int m = 0, lm = 0;
	if (lb > 1)
		while (m * K + (1 << lm) * lm < lb) {
			m++;
			if (1 << lm < m)
				lm++;
		}
	int m_ = 1 << lm;
	int uu[(N + M) * K], uu_[N_ * K], ww[K];
	for (int i = 0; i < n * K; i++)
		uu[i] = i;
	for (int j = 0; j < m * K; j++)
		uu[(n + m - 1 - j / K) * K + j % K] = la + j;
	mode = 0;
	semisort(uu, n + m);
	for (int k = 0; k < K; k++)
		ww[k] = ZERO;
	for (int h = 0; h < n + m; h++) {
		set(ww, uu + h * K, gate(OP_EQUAL, uu[h * K + K - 1], ZERO));
		set(uu + h * K, ww, gate(OP_EQUAL, uu[h * K + K - 1], ONE));
	}
	unsemisort(uu, n + m);
	for (int j = 0; j < m_ * K; j++)
		uu_[j] = j < m * K ? uu[n * K + (m - 1 - j / K) * K + j % K] : ZERO;
	idx = la + m * K, apply_perm(uu_, lm);
	for (int j = 0; j < m * K; j++)
		uu[n * K + (m - 1 - j / K) * K + j % K] = uu_[j];
	mode = 1;
	semisort(uu, n + m);
	for (int k = 0; k < K; k++)
		ww[k] = ZERO;
	for (int h = 0; h < n + m; h++) {
		add(ww, uu + h * K, gate(OP_EQUAL, uu[h * K + K - 1], ONE));
		set(uu + h * K, ww, gate(OP_EQUAL, uu[h * K + K - 1], ZERO));
		clear(ww, gate(OP_EQUAL, uu[h * K + K - 1], ZERO));
	}
	unsemisort(uu, n + m);
	for (int i = 0; i < n_ * K; i++)
		uu_[i] = i < n * K ? uu[i] : ZERO;
	idx = n * K, apply_perm(uu_, ln);
	for (int i = 0; i < n * K; i++)
		uu[i] = uu_[i];
	for (int i = 0; i < n; i++)
		for (int k = 0; k < KY; k++)
			cc[i][k] = uu[i * K + KX * 2 + k];
	return lc;
}

Compilation message (stderr)

abc.cpp: In lambda function:
abc.cpp:59:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   59 |    vv[ii[h] & n - 1] = h;
      |               ~~^~~
abc.cpp:64:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   64 |     int h_ = vv[ii[h ^ m] & n - 1 ^ m];
      |                             ~~^~~
abc.cpp:64:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   64 |     int h_ = vv[ii[h ^ m] & n - 1 ^ m];
      |                 ~~~~~~~~~~^~~~~~~
abc.cpp:68:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   68 |      ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
      |                ~~^~~
abc.cpp:68:46: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   68 |      ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
      |                                            ~~^~~
abc.cpp: In lambda function:
abc.cpp:148:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  148 |    vv[ii[h] & n - 1] = h;
      |               ~~^~~
abc.cpp:153:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  153 |     int h_ = vv[ii[h ^ m] & n - 1 ^ m];
      |                             ~~^~~
abc.cpp:153:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  153 |     int h_ = vv[ii[h ^ m] & n - 1 ^ m];
      |                 ~~~~~~~~~~^~~~~~~
abc.cpp:157:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  157 |      ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
      |                ~~^~~
abc.cpp:157:46: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  157 |      ii[vv[j & n - 1] = h_] = j, ii[vv[i & n - 1] = h_ ^ m] = i;
      |                                            ~~^~~
abc.cpp: In lambda function:
abc.cpp:290:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  290 |   while (1 << l + 1 < n)
      |               ~~^~~
abc.cpp: In lambda function:
abc.cpp:300:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  300 |   while (1 << l + 1 < n)
      |               ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24
• Subtask 6: 6 / 6
• Subtask 7: 18 / 18
• Subtask 8: 10 / 10
• Subtask 9: 6 / 6