#include <bits/stdc++.h>
// #include "abc.h"
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
// 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
const int LEN = 16, MXC = 26;
const int MXN = 2048;
namespace STRING {
const int FOOL = 524287;
int CVT(string s) {
int ans = 0;
for (auto &i : s) ans = ans * MXC + (i - 'a');
if (s.size() > 1) ans += MXC;
if (s.size() > 2) ans += MXC * MXC;
if (s.size() > 3) ans += MXC * MXC * MXC;
return ans;
}
}
struct P {
int a, b, val, t;
P() {}
P(int _a, int _b, int _v, int _t) : a(_a), b(_b), val(_v), t(_t) {}
};
struct PP {
int pa, pb, pv, pt;
PP() {}
PP(int _a, int _b, int _v, int _t) : pa(_a), pb(_b), pv(_v), pt(_t) {}
};
namespace PERMUTATION {
vector<int> v[MXN];
string s;
void PERM(int l, int r) {
int n = r - l;
if (n == 1) return;
int x = n / 2;
FOR(i, l, r) v[i].push_back(v[i].back() % n);
vector<int> a(n);
FOR(i, l, r) a[i - l] = v[i].back();
vector<pii> edge(n), e(x, mp(-1, -1));
FOR(i, 0, n) {
int id = a[i] % x;
if (e[id].fs == -1) e[id].fs = i;
else e[id].sc = i;
}
FOR(i, 0, x) {
edge[i].fs = i + x;
edge[i + x].fs = i;
edge[e[i].fs].sc = e[i].sc;
edge[e[i].sc].sc = e[i].fs;
}
vector<bool> b(n);
vector<int> cyc;
auto CYC = [&](int sr) {
cyc.push_back(sr);
cyc.push_back(edge[sr].fs);
int p = sr, now = edge[sr].fs;
b[p] = true;
b[now] = true;
while (true) {
int nxt = (edge[now].fs ^ edge[now].sc ^ p);
if (nxt == sr) break;
cyc.push_back(nxt);
p = now;
now = nxt;
b[nxt] = true;
}
};
FOR(i, 0, x) {
if (b[i]) continue;
CYC(i);
}
string t(x, '0');
for (int i = 0; i < n; i += 2) {
if (cyc[i] >= x) {
t[cyc[i] - x] = '1';
swap(v[l + cyc[i]], v[l + cyc[i] - x]);
}
}
s += t;
PERM(l, l + x);
PERM(l + x, r);
FOR(i, 0, x) {
if (v[l + i].back() > v[l + x + i].back()) {
swap(v[l + i], v[l + x + i]);
s.push_back('1');
} else {
s.push_back('0');
}
}
FOR(i, l, r) v[i].pop_back();
}
string DO(vector<int> &a) {
int n = a.size();
FOR(i, 0, n) {
v[i].clear();
v[i].push_back(a[i]);
}
s.clear();
PERM(0, n);
return s;
}
}
int CALC_LEN(int x) {
int n = (1 << (__lg(x - 1) + 1));
return x * 55 + (n * __lg(n));
}
int BSH_LEN(int x) {
int l = 2, r = 2049;
while (l + 1 < r) {
int mid = (l + r) >> 1;
(CALC_LEN(mid) <= x ? l : r) = mid;
}
return l;
}
// Alice
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs_alice[]
) {
vector<pair<P, int>> v(n);
FOR(i, 0, n) v[i] = mp(P(STRING::CVT(string(names[i])), STRING::CVT(string(names[i])), numbers[i], 0), i);
v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 0), n));
v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 0), n + 1));
int nn = v.size();
sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
return a.fs.a > b.fs.a;
});
vector<int> p;
FOR(i, 0, nn) p.push_back(v[i].sc);
auto check = [&]() {
int x = p.size();
return ((1 << __lg(x)) == x);
};
while (!check()) p.push_back(p.size());
string s = PERMUTATION::DO(p);
int cnt = 0;
auto PUT = [&](int x, int len) {
FOR(i, 0, len) {
outputs_alice[cnt] = ((x & (1 << i)) ? 1 : 0);
cnt++;
}
};
FOR(i, 0, nn) {
PUT(v[i].fs.a, 19);
PUT(v[i].fs.b, 19);
PUT(v[i].fs.val, LEN);
PUT(v[i].fs.t, 1);
}
for (auto &i : s) {
outputs_alice[cnt] = (i & 1);
cnt++;
}
return cnt;
}
// Bob
int // returns lb
bob(
/* in */ const int m,
/* in */ const char senders[][5],
/* in */ const char recipients[][5],
/* out */ bool outputs_bob[]
) {
vector<pair<P, int>> v(m);
FOR(i, 0, m) v[i] = mp(P(STRING::CVT(string(senders[i])), STRING::CVT(recipients[i]), 0, 1), 0);
v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 1), 0));
v.push_back(mp(P(STRING::FOOL, STRING::FOOL, 0, 1), 0));
// m = v.size();
int mm = v.size();
sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
return a.fs.b < b.fs.b;
});
FOR(i, 0, mm) v[i].sc = i;
sort(v.begin(), v.end(), [](pair<P, int> a, pair<P, int> b) {
return a.fs.a < b.fs.a;
});
vector<int> p;
FOR(i, 0, mm) p.push_back(v[i].sc);
auto check = [&]() {
int x = p.size();
return ((1 << __lg(x)) == x);
};
while (!check()) p.push_back(p.size());
string s = PERMUTATION::DO(p);
int cnt = 0;
auto PUT = [&](int x, int len) {
FOR(i, 0, len) {
outputs_bob[cnt] = ((x & (1 << i)) ? 1 : 0);
cnt++;
}
};
FOR(i, 0, mm) {
PUT(v[i].fs.a, 19);
PUT(v[i].fs.b, 19);
PUT(v[i].fs.val, LEN);
PUT(v[i].fs.t, 1);
}
for (auto &i : s) {
outputs_bob[cnt] = (i & 1);
cnt++;
}
return cnt;
}
// Circuit
int // returns l
circuit(
/* in */ const int la,
/* in */ const int lb,
/* out */ int operations[],
/* out */ int operands[][2],
/* out */ int outputs_circuit[][16]
) {
int na = BSH_LEN(la), nb = BSH_LEN(lb);
int cnt = la + lb;
int sa = na * 55, sb = la + nb * 55;
int na_ = 2 << (__lg(na - 1)), nb_ = 2 << (__lg(nb - 1));
// cout << na << ' ' << nb << endl;
vector<PP> v;
FOR(i, 0, na) v.push_back(PP(0 + i * 55 + 0, 0 + i * 55 + 19, 0 + i * 55 + 38, 0 + i * 55 + 54));
FOR(i, 0, nb) v.push_back(PP(la + i * 55 + 0, la + i * 55 + 19, la + i * 55 + 38, la + i * 55 + 54));
P msk1 = P(1, 0, 0, 1), msk2 = P(0, 1, 0, 1);
vector<int> cmp_bit;
auto add_op = [&](int input_a, int input_b, int op) {
operations[cnt] = op;
operands[cnt][0] = input_a, operands[cnt][1] = input_b;
return cnt++;
};
auto add_ops = [&](int inputs_a, int inputs_b, int op, int len) {
int pos = cnt;
FOR(i, 0, len) {
add_op(inputs_a + i, inputs_b + i, op);
}
return pos;
};
auto add_op_obj = [&](PP a, PP b, int op) {
int pos = cnt;
FOR(i, 0, 19) add_op(a.pa + i, b.pa + i, op);
FOR(i, 0, 19) add_op(a.pb + i, b.pb + i, op);
FOR(i, 0, LEN) add_op(a.pv + i, b.pv + i, op);
FOR(i, 0, 1) add_op(a.pt + i, b.pt + i, op);
return PP(pos + 0, pos + 19, pos + 38, pos + 54);
};
auto add_op_1 = [&](int inputs_a, int input_b, int op, int len) {
int pos = cnt;
FOR(i, 0, len) {
add_op(inputs_a + i, input_b, op);
}
return pos;
};
auto add_op_obj_1 = [&](PP a, int b, int op) {
int pos = cnt;
FOR(i, 0, 19) add_op(a.pa + i, b, op);
FOR(i, 0, 19) add_op(a.pb + i, b, op);
FOR(i, 0, LEN) add_op(a.pv + i, b, op);
FOR(i, 0, 1) add_op(a.pt + i, b, op);
return PP(pos + 0, pos + 19, pos + 38, pos + 54);
};
while (v.size() != 2048) {
v.push_back(PP(add_ops(0, 0, OP_ONE, 19), add_ops(0, 0, OP_ONE, 19), add_ops(0, 0, OP_ZERO, LEN), add_op(0, 0, OP_ONE)));
}
auto adder = [&](int inputs_a, int inputs_b, int len) {
int c = 54, c1, c2, g1;
vector<int> vc, vg;
FOR(i, 0, len) {
int a = inputs_a + i, b = inputs_b + i;
c1 = add_op(a, b, OP_AND);
g1 = add_op(a, b, OP_XOR);
c2 = add_op(c, g1, OP_AND);
vc.push_back(c);
vg.push_back(g1);
c = add_op(c1, c2, OP_OR);
}
int pos = cnt;
FOR(i, 0, len) {
add_op(vg[i], vc[i], OP_XOR);
}
return pos;
};
auto CMP = [&](PP a, PP b, P mask) {
int p = 54;
if (mask.t) {
FOR(i, 0, 1) {
int l = a.pt + i, r = b.pt + i;
int s = add_op(l, r, OP_XOR);
p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
}
}
if (mask.b) {
FOR(i, 0, 19) {
int l = a.pb + i, r = b.pb + i;
int s = add_op(l, r, OP_XOR);
p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
}
}
if (mask.a) {
FOR(i, 0, 19) {
int l = a.pa + i, r = b.pa + i;
int s = add_op(l, r, OP_XOR);
p = add_op(add_op(l, s, OP_AND), add_op(p, s, OP_GREATER), OP_OR);
}
}
return p;
};
auto SWAP = [&](int &a, int &b, int s, int len) {
int x = add_op_1(a, s, OP_GREATER, len), y = add_op_1(b, s, OP_AND, len);
int c = add_ops(x, y, OP_OR, len);
int d = add_ops(c, a, OP_XOR, len);
int e = add_ops(d, b, OP_XOR, len);
a = c, b = e;
};
auto SWAP_OBJ = [&](PP &a, PP &b, int s) {
PP x = add_op_obj_1(a, s, OP_GREATER), y = add_op_obj_1(b, s, OP_AND);
PP c = add_op_obj(x, y, OP_OR);
PP d = add_op_obj(c, a, OP_XOR);
PP e = add_op_obj(d, b, OP_XOR);
a = c, b = e;
};
auto bitonic_sort = [&](auto self, int l, int r, P mask) {
if (l + 1 == r) return;
int x = (r - l) >> 1;
FOR(i, 0, x) {
cmp_bit.push_back(CMP(v[l + i], v[l + x + i], mask));
SWAP_OBJ(v[l + i], v[l + x + i], cmp_bit.back());
}
self(self, l, l + x, mask);
self(self, l + x, r, mask);
};
auto bitonic_undo = [&](auto self, int l, int r) {
if (l + 1 == r) return;
int x = (r - l) >> 1;
self(self, l + x, r);
self(self, l, l + x);
for (int i = x - 1; i >= 0; i--) {
SWAP_OBJ(v[l + i], v[l + x + i], cmp_bit.back());
cmp_bit.pop_back();
}
};
auto SHIFT = [&](auto self, int l, int r, int s, int &ptr) {
if (l + 1 == r) return;
int x = (r - l) >> 1;
FOR(i, 0, x) {
SWAP_OBJ(v[l + i], v[l + x + i], s + ptr);
ptr++;
}
self(self, l, l + x, s, ptr);
self(self, l + x, r, s, ptr);
FOR(i, 0, x) {
SWAP_OBJ(v[l + i], v[l + x + i], s + ptr);
ptr++;
}
};
auto SWEEP1 = [&]() {
int x = add_op_1(0, 0, OP_ZERO, LEN);
FOR(i, 0, MXN) {
int &val = v[i].pv, s = v[i].pt;
int tmp = add_ops(add_op_1(x, s, OP_AND, LEN), add_op_1(val, s, OP_GREATER, LEN), OP_OR, LEN);
int tmp2 = add_ops(tmp, tmp, OP_AND, LEN);
x = tmp, val = tmp2;
}
};
auto SWEEP2 = [&]() {
int x = add_op_1(0, 0, OP_ZERO, LEN);
FOR(i, 0, MXN) {
int &val = v[i].pv, s = v[i].pt;
val = add_op_1(val, s, OP_AND, LEN);
SWAP(x, val, s, LEN);
val = adder(x, val, LEN);
x = add_op_1(x, 0, OP_ZERO, LEN);
SWAP(x, val, s, LEN);
}
};
bitonic_sort(bitonic_sort, 0, MXN, msk1);
SWEEP1();
bitonic_undo(bitonic_undo, 0, MXN);
int ptr = 0;
SHIFT(SHIFT, na, na + nb_, sb, ptr);
FOR(i, 0, MXN) {
int &id = v[i].pt;
id = add_op(id, 0, OP_NOT_X0);
}
bitonic_sort(bitonic_sort, 0, MXN, msk2);
FOR(i, 0, MXN) {
int &id = v[i].pt;
id = add_op(id, 0, OP_NOT_X0);
}
SWEEP2();
bitonic_undo(bitonic_undo, 0, MXN);
ptr = 0;
SHIFT(SHIFT, 0, 0 + na_, sa, ptr);
FOR(i, 0, na - 2) {
int id = v[i].pv;
FOR(j, 0, LEN) outputs_circuit[i][j] = id + j;
}
return cnt;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
296372 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
296372 KB |
Correct! |
| 2 |
Correct |
160 ms |
296828 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
296372 KB |
Correct! |
| 2 |
Correct |
160 ms |
296828 KB |
Correct! |
| 3 |
Correct |
374 ms |
373256 KB |
Correct! |
| 4 |
Correct |
367 ms |
373480 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
298476 KB |
Correct! |
| 2 |
Correct |
321 ms |
365928 KB |
Correct! |
| 3 |
Correct |
348 ms |
368728 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
298476 KB |
Correct! |
| 2 |
Correct |
321 ms |
365928 KB |
Correct! |
| 3 |
Correct |
348 ms |
368728 KB |
Correct! |
| 4 |
Correct |
333 ms |
365608 KB |
Correct! |
| 5 |
Correct |
346 ms |
368804 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
298476 KB |
Correct! |
| 2 |
Correct |
321 ms |
365928 KB |
Correct! |
| 3 |
Correct |
348 ms |
368728 KB |
Correct! |
| 4 |
Correct |
333 ms |
365608 KB |
Correct! |
| 5 |
Correct |
346 ms |
368804 KB |
Correct! |
| 6 |
Correct |
265 ms |
334880 KB |
Correct! |
| 7 |
Correct |
374 ms |
373196 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
450 ms |
506304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
450 ms |
506304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
296372 KB |
Correct! |
| 2 |
Correct |
160 ms |
296828 KB |
Correct! |
| 3 |
Correct |
374 ms |
373256 KB |
Correct! |
| 4 |
Correct |
367 ms |
373480 KB |
Correct! |
| 5 |
Correct |
164 ms |
298476 KB |
Correct! |
| 6 |
Correct |
321 ms |
365928 KB |
Correct! |
| 7 |
Correct |
348 ms |
368728 KB |
Correct! |
| 8 |
Correct |
333 ms |
365608 KB |
Correct! |
| 9 |
Correct |
346 ms |
368804 KB |
Correct! |
| 10 |
Correct |
265 ms |
334880 KB |
Correct! |
| 11 |
Correct |
374 ms |
373196 KB |
Correct! |
| 12 |
Runtime error |
450 ms |
506304 KB |
Execution killed with signal 11 |
| 13 |
Halted |
0 ms |
0 KB |
- |
