/* -A2 --indent=tab=4 --indent-classes --indent-switches --indent-namespaces --indent-preprocessor -xg -p -xd -H -xj -xe read all problems do first-eye problems read rev order uhhh dont fail impl */ #include <bits/stdc++.h> #include "abc.h" #define re(a, b, c, d) for (auto a = b; a <= c; a += d) #define de(a, b, c, d) for (auto a = b; a >= c; a -= d) #define ms(a, b) memset(a, b, sizeof (a)) #define wh(a) while (a --) #define PII pair <int, int> #define F first #define S second #define pb push_back #define eb emplace_back template <typename T> bool chkmin (T &a, T b) { return (b < a) ? a = b, 1 : 0; } template <typename T> bool chkmax (T &a, T b) { return (b > a) ? a = b, 1 : 0; } using namespace std; const int N = 1e5 + 5; // 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 // Alice int // returns la alice ( /* in */ const int n, /* in */ const char names[][5], /* in */ const unsigned short numbers[], /* out */ bool outputs_alice[] ) { outputs_alice[0] = 0; outputs_alice[1] = 1; int cur = 2, mod = (1 << 16); re (i, 0, n - 1, 1) { int tmp = numbers[i]; re (lg, 0, 9, 1) { re (j, 0, n - 1, 1) outputs_alice[cur++] = tmp & (1 << j); tmp = (tmp * 2) % mod; } } for (int i = 0; i < 16; i++) outputs_alice[cur++] = 0; return cur; } // Bob int // returns lb bob ( /* in */ const int m, /* in */ const char senders[][5], /* in */ const char recipients[][5], /* out */ bool outputs_bob[] ) { vector<vector<int>> f (26, vector<int> (26, 0)); for (int i = 0; i < m; i ++) f[senders[i][0] - 'a'][recipients[i][0] - 'a']++; int cnt = 0; for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) for (int k = 0; k < 10; k++) outputs_bob[cnt++] = f[i][j] & (1 << k); return cnt; } // Circuit int cnt, zero, one, n, m; int upd (int a, int b, int operations[], int operands[][2]) { int rem = zero; vector<int> v; re (i, 0, 15, 1) { operations[cnt] = OP_XOR; operands[cnt][0] = a + i; operands[cnt][1] = b + i; int fxor = cnt++; operations[cnt] = OP_XOR; operands[cnt][0] = fxor; operands[cnt][1] = rem; v.push_back (cnt); int cxor = cnt++; operations[cnt] = OP_AND; operands[cnt][0] = a + i; operands[cnt][1] = b + i; int fand = cnt++; operations[cnt] = OP_AND; operands[cnt][0] = fxor; operands[cnt][1] = rem; int lst = cnt++; operations[cnt] = OP_OR; operands[cnt][0] = fand; operands[cnt][1] = lst; rem = cnt++; } int sv = cnt; re (i, 0, 15, 1) { operations[cnt] = OP_X0; operands[cnt][0] = v[i]; operands[cnt][1] = v[i]; cnt++; } return sv; } int qry (int a, int b, int operations[], int operands[][2]) { int sv = cnt; re (i, 0, 15, 1) { operations[cnt] = OP_AND; operands[cnt][0] = a + i; operands[cnt][1] = b; cnt++; } return sv; } int // returns l circuit ( /* in */ const int la, /* in */ const int lb, /* out */ int operations[], /* out */ int operands[][2], /* out */ int outputs_circuit[][16] ) { n = (la - 18) / 160; cnt = la + lb; zero = 0; one = 1; vector<int> cur (n), num (n); re (i, 0, n - 1, 1) cur[i] = 2 + n * 160, num[i] = 2 + i * 160; re (i, 0, n - 1, 1) { re (j, 0, n - 1, 1) { int x = la + (n * i + j) * 10; re (k, 0, 9, 1) { int t = qry (num[i] + 16 * k, x + k, operations, operands); cur[j] = upd (cur[j], t, operations, operands); } } } re (i, 0, n - 1, 1) re (j, 0, 15, 1) outputs_circuit[i][j] = cur[i] + j; return cnt; }