#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 {
string s;
void PERM(vector<int> v, int dep) {
int n = v.size();
// cout << string(2 * dep, ' ') << n << ' ' << s.size() << endl;
if (n == 1) return;
int odd = n % 2;
if (odd) v.push_back(n++);
int x = n / 2;
vector<pii> edge(n), e(x, mp(-1, -1));
FOR(i, 0, n) {
int id = v[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) {
int p = sr, now = edge[sr].fs;
b[p] = true;
b[now] = true;
cyc.push_back(p);
cyc.push_back(now);
while (true) {
int nxt = (edge[now].fs ^ edge[now].sc ^ p);
if (nxt == sr) break;
b[nxt] = true;
cyc.push_back(nxt);
p = now;
now = nxt;
}
};
for (int i = x - 1; i >= 0; i--) {
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[cyc[i]], v[cyc[i] - x]);
}
}
if (odd) t.pop_back();
// cout << t.size() << endl;
s += t;
vector<int> vl, vr;
FOR(i, 0, x) vl.push_back(v[i] % x);
FOR(i, x, n - odd) vr.push_back(v[i] % x);
// cout << string(2 * dep, ' ') << vr.size() << endl;
PERM(vl, dep + 1);
PERM(vr, dep + 1);
vector<pii> vpl, vpr;
FOR(i, 0, x) vpl.push_back(mp(vl[i], v[i]));
FOR(i, x, n - odd) vpr.push_back(mp(vr[i - x], v[i]));
sort(vpl.begin(), vpl.end());
sort(vpr.begin(), vpr.end());
FOR(i, 0, vr.size()) s.push_back((vpl[i].sc > vpr[i].sc) ? '1' : '0');
// cout << string(2 * dep, ' ') << n << ' ' << s.size() << endl;
}
string DO(vector<int> &a) {
s.clear();
PERM(a, 0);
return s;
}
}
int dp[MXN];
void LEN_INIT() {
dp[0] = 0;
dp[1] = 0;
FOR(i, 2, MXN) {
dp[i] = i / 2 * 2 + dp[i / 2] + dp[(i + 1) / 2];
}
// cout << "DP: ";
// cout << dp[7] << endl;
}
int BSH_LEN(int x) {
int l = 2, r = 2049;
while (l + 1 < r) {
int mid = (l + r) >> 1;
((mid * 55 + dp[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);
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);
}
// cout << s.size() << endl;
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));
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);
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]
) {
LEN_INIT();
int na = BSH_LEN(la), nb = BSH_LEN(lb);
int cnt = la + lb;
int sa = na * 55, sb = la + nb * 55;
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 n = r - l;
int x = n >> 1;
int mid = l + x + (n & 1);
FOR(i, 0, x) {
SWAP_OBJ(v[l + i], v[mid + i], s + ptr);
ptr++;
}
self(self, l, mid, s, ptr);
self(self, mid, r, s, ptr);
FOR(i, 0, x) {
SWAP_OBJ(v[l + i], v[mid + 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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
294960 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
294960 KB |
Correct! |
| 2 |
Correct |
205 ms |
294868 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
294960 KB |
Correct! |
| 2 |
Correct |
205 ms |
294868 KB |
Correct! |
| 3 |
Correct |
425 ms |
370648 KB |
Correct! |
| 4 |
Correct |
412 ms |
371004 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
191 ms |
297080 KB |
Correct! |
| 2 |
Correct |
312 ms |
333188 KB |
Correct! |
| 3 |
Correct |
348 ms |
345976 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
191 ms |
297080 KB |
Correct! |
| 2 |
Correct |
312 ms |
333188 KB |
Correct! |
| 3 |
Correct |
348 ms |
345976 KB |
Correct! |
| 4 |
Correct |
330 ms |
333444 KB |
Correct! |
| 5 |
Correct |
357 ms |
344480 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
191 ms |
297080 KB |
Correct! |
| 2 |
Correct |
312 ms |
333188 KB |
Correct! |
| 3 |
Correct |
348 ms |
345976 KB |
Correct! |
| 4 |
Correct |
330 ms |
333444 KB |
Correct! |
| 5 |
Correct |
357 ms |
344480 KB |
Correct! |
| 6 |
Correct |
307 ms |
326900 KB |
Correct! |
| 7 |
Correct |
437 ms |
364508 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
619 ms |
426036 KB |
Correct! |
| 2 |
Correct |
619 ms |
424040 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
619 ms |
426036 KB |
Correct! |
| 2 |
Correct |
619 ms |
424040 KB |
Correct! |
| 3 |
Correct |
621 ms |
413564 KB |
Correct! |
| 4 |
Correct |
657 ms |
425100 KB |
Correct! |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
294960 KB |
Correct! |
| 2 |
Correct |
205 ms |
294868 KB |
Correct! |
| 3 |
Correct |
425 ms |
370648 KB |
Correct! |
| 4 |
Correct |
412 ms |
371004 KB |
Correct! |
| 5 |
Correct |
191 ms |
297080 KB |
Correct! |
| 6 |
Correct |
312 ms |
333188 KB |
Correct! |
| 7 |
Correct |
348 ms |
345976 KB |
Correct! |
| 8 |
Correct |
330 ms |
333444 KB |
Correct! |
| 9 |
Correct |
357 ms |
344480 KB |
Correct! |
| 10 |
Correct |
307 ms |
326900 KB |
Correct! |
| 11 |
Correct |
437 ms |
364508 KB |
Correct! |
| 12 |
Correct |
619 ms |
426036 KB |
Correct! |
| 13 |
Correct |
619 ms |
424040 KB |
Correct! |
| 14 |
Correct |
621 ms |
413564 KB |
Correct! |
| 15 |
Correct |
657 ms |
425100 KB |
Correct! |
| 16 |
Correct |
649 ms |
425824 KB |
Correct! |
| 17 |
Correct |
657 ms |
427528 KB |
Correct! |
