oj.uz

답안 #777255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777255 2023-07-08T22:13:17 Z rainboy 앨리스, 밥, 서킷 (APIO23_abc) C++17
100 / 100
 657 ms 325796 KB 
/* 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

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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1820 KB Correct!

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1820 KB Correct!
2 Correct 3 ms 1824 KB Correct!

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1820 KB Correct!
2 Correct 3 ms 1824 KB Correct!
3 Correct 299 ms 175112 KB Correct!
4 Correct 296 ms 175692 KB Correct!

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6200 KB Correct!
2 Correct 199 ms 113564 KB Correct!
3 Correct 232 ms 133196 KB Correct!

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6200 KB Correct!
2 Correct 199 ms 113564 KB Correct!
3 Correct 232 ms 133196 KB Correct!
4 Correct 207 ms 113580 KB Correct!
5 Correct 247 ms 132964 KB Correct!

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6200 KB Correct!
2 Correct 199 ms 113564 KB Correct!
3 Correct 232 ms 133196 KB Correct!
4 Correct 207 ms 113580 KB Correct!
5 Correct 247 ms 132964 KB Correct!
6 Correct 156 ms 77624 KB Correct!
7 Correct 311 ms 165480 KB Correct!

Subtask #7
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 657 ms 321892 KB Correct!
2 Correct 600 ms 322300 KB Correct!

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 657 ms 321892 KB Correct!
2 Correct 600 ms 322300 KB Correct!
3 Correct 600 ms 306180 KB Correct!
4 Correct 622 ms 322144 KB Correct!

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1820 KB Correct!
2 Correct 3 ms 1824 KB Correct!
3 Correct 299 ms 175112 KB Correct!
4 Correct 296 ms 175692 KB Correct!
5 Correct 11 ms 6200 KB Correct!
6 Correct 199 ms 113564 KB Correct!
7 Correct 232 ms 133196 KB Correct!
8 Correct 207 ms 113580 KB Correct!
9 Correct 247 ms 132964 KB Correct!
10 Correct 156 ms 77624 KB Correct!
11 Correct 311 ms 165480 KB Correct!
12 Correct 657 ms 321892 KB Correct!
13 Correct 600 ms 322300 KB Correct!
14 Correct 600 ms 306180 KB Correct!
15 Correct 622 ms 322144 KB Correct!
16 Correct 619 ms 325624 KB Correct!
17 Correct 630 ms 325796 KB Correct!