#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "abc.h"
using namespace std;
#ifdef WAIMAI
#include "grader.cpp"
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
// 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 DS_LEN = 55;
const int X_LEN = 19;
const int Y_LEN = 19;
const int W_LEN = 16;
struct ds {
int x, y, w, t;
ds() {}
ds(int x, int y, int w, int t) : x(x), y(y), w(w), t(t) {}
} a[2400];
string perm_str(vector<int> id) {
int n = id.size();
if (n == 0) return "";
vector<int> p(n), val, tag(n);
vector<vector<pair<int, int>>> st(n);
string res;
val = id;
auto rec = [&](auto rec, int l, int r)->void {
if (l == r) return;
int mid = (l + r) / 2, len = mid - l + 1;
fill(tag.begin() + l, tag.begin() + mid + 1, 0);
FOR (i, l, r) p[val[i]] = i;
auto check = [&](int i) {
tag[i] = 1;
while (true) {
int x = val[i];
int y = (x < len ? x + len : x - len);
if (y > r) break;
if (p[y] <= mid) {
if (tag[p[y]] != 0) break;
tag[p[y]] = 2;
i = p[y] + len;
} else {
if (tag[p[y] - len] != 0) break;
tag[p[y] - len] = 1;
i = p[y] - len;
}
}
};
check(mid);
FOR (i, l, mid) if (i + len <= r) {
if (tag[i] == 0) check(i);
if (tag[i] == 1) res += "0";
else {
res += "1";
swap(id[i], id[i + len]);
swap(val[i], val[i + len]);
}
}
FOR (i, l, r) if (val[i] >= len) {
val[i] -= len;
st[id[i]].pb(l, r);
}
rec(rec, l, mid);
rec(rec, mid + 1, r);
FOR (i, l, r) if (st[id[i]].size() && st[id[i]].back() == make_pair(l, r)) {
val[i] += len;
st[id[i]].pop_back();
}
FOR (i, l, mid) if (i + len <= r) {
if (val[i] < val[i + len]) res += "0";
else {
res += "1";
swap(id[i], id[i + len]);
swap(val[i], val[i + len]);
}
}
};
rec(rec, 0, n - 1);
return res;
}
string perm_str(vector<int> lid, vector<int> rid) {
int n = lid.size();
vector<int> id(n), inv(n);
FOR (i, 0, n - 1) inv[rid[i]] = i;
FOR (i, 0, n - 1) id[i] = inv[lid[i]];
return perm_str(id);
}
int conv(const char s[]) {
int val = 0, n = 0;
for (int i = 0; s[i] != '\0'; i++) {
n++;
val = 26 * val + s[i] - 'a';
}
if (n == 1) return 1 + val;
if (n == 2) return 1 + 26 + val;
if (n == 3) return 1 + 26 + 26 * 26 + val;
if (n == 4) return 1 + 26 + 26 * 26 + 26 * 26 * 26 + val;
}
// Alice, n <= 700
int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int l, int r) {
return conv(names[l]) < conv(names[r]);
});
int la = 0;
auto gen = [&](int x, int len) {
FOR (i, 0, len - 1) outputs_alice[la++] = (x >> i & 1);
};
FOR (i, 0, n - 1) {
gen(conv(names[id[i]]), X_LEN);
gen(conv(names[id[i]]), Y_LEN);
gen(numbers[id[i]] , W_LEN);
gen(0 , 1 );
}
string res = perm_str(id);
for (char c : res) gen(c - '0', 1);
return la;
}
// Bob, m <= 1000
int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]) {
vector<int> xid(m), yid(m);
iota(xid.begin(), xid.end(), 0);
iota(yid.begin(), yid.end(), 0);
sort(xid.begin(), xid.end(), [&](int l, int r) {
return conv(senders[l]) < conv(senders[r]);
});
sort(yid.begin(), yid.end(), [&](int l, int r) {
return conv(recipients[l]) < conv(recipients[r]);
});
int lb = 0;
auto gen = [&](int x, int len) {
FOR (i, 0, len - 1) outputs_bob[lb++] = (x >> i & 1);
};
FOR (i, 0, m - 1) {
gen(conv(senders[xid[i]]) , X_LEN);
gen(conv(recipients[xid[i]]), Y_LEN);
gen(0 , W_LEN);
gen(1 , 1 );
}
string res = perm_str(xid, yid);
for (char c : res) gen(c - '0', 1);
return lb;
}
// Circuit
int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]) {
auto get_n = [&](int len) {
auto cal = [&](int n) {
if (n == 0) return 0;
int sz = DS_LEN * n;
queue<int> q;
q.push(n);
while (q.size()) {
int x = q.front();
q.pop();
if (x == 1) continue;
sz += x - (x & 1);
q.push(x >> 1);
q.push((x + 1) >> 1);
}
return sz;
};
int l = 0, r = 1000;
while (l < r) {
int mid = (l + r) / 2;
if (cal(mid) >= len) r = mid;
else l = mid + 1;
}
return l;
};
int n = get_n(la), m = get_n(lb), lc = la + lb;
if (n == 0) return 0;
auto op = [&](int ty, int x, int y) {
operations[lc] = ty;
operands[lc][0] = x;
operands[lc][1] = y;
return lc++;
};
auto opf = [&](int ty, int x, int f, int len) {
int s = lc;
FOR (i, 0, len - 1) op(ty, x + i, f);
return s;
};
auto ops = [&](int ty, int x, int y, int len) {
int s = lc;
FOR (i, 0, len - 1) op(ty, x + i, y + i);
return s;
};
if (m == 0) {
FOR (i, 0, n - 1) FOR (j, 0, W_LEN - 1) outputs_circuit[i][j] = op(OP_ZERO, 0, 0);
return lc;
}
FOR (i, 0, n - 1) {
int pre = DS_LEN * i;
a[i] = ds(pre, pre + X_LEN, pre + X_LEN + Y_LEN, pre + X_LEN + Y_LEN + W_LEN);
}
FOR (i, 0, m - 1) {
int pre = la + DS_LEN * i;
a[n + i] = ds(pre, pre + X_LEN, pre + X_LEN + Y_LEN, pre + X_LEN + Y_LEN + W_LEN);
}
int sz = 1;
while (sz < n + m) sz <<= 1;
vector<int> id(sz, -1), st;
FOR (i, 0, n - 1) id[i] = i;
FOR (i, 0, m - 1) id[sz - i - 1] = n + i;
auto swaps = [&](int &x, int &y, int f, int len) {
int xf, yf, z, nx, ny;
xf = opf(OP_GREATER, x , f , len);
yf = opf(OP_AND , y , f , len);
nx = ops(OP_OR , xf, yf, len);
z = ops(OP_XOR , y , nx, len);
ny = ops(OP_XOR , x , z , len);
x = nx, y = ny;
};
auto swap_a = [&](int x, int y, int f) {
swaps(a[x].x, a[y].x, f, X_LEN);
swaps(a[x].y, a[y].y, f, Y_LEN);
swaps(a[x].w, a[y].w, f, W_LEN);
swaps(a[x].t, a[y].t, f, 1 );
};
auto comp = [&](int x, int y, bool isy) {
int px = (isy == 0 ? a[x].x : a[x].y);
int py = (isy == 0 ? a[y].x : a[y].y);
int lsml, lbig;
for (int i = X_LEN - 1; i >= 0; i--) {
int sml = op(OP_LESS , px + i, py + i);
int big = op(OP_GREATER, px + i, py + i);
if (i != X_LEN - 1) {
sml = op(OP_GREATER, sml, lbig);
big = op(OP_GREATER, big, lsml);
sml = op(OP_OR , sml, lsml);
big = op(OP_OR , big, lbig);
}
lsml = sml, lbig = big;
}
if (isy == 0) {
int big = op(OP_GREATER, a[x].t, a[y].t);
big = op(OP_GREATER, big, lsml);
lbig = op(OP_OR , big, lbig);
} else {
int big = op(OP_LESS, a[x].t, a[y].t);
big = op(OP_GREATER, big, lsml);
lbig = op(OP_OR , big, lbig);
}
st.pb(lbig);
swap_a(x, y, lbig);
};
auto merge = [&](auto merge, int l, int r, bool isy)->void {
if (l == r) return;
int mid = (l + r) / 2, len = mid - l + 1;
FOR (i, l, mid) {
if (id[i + len] == -1) {
st.pb(0);
continue;
}
if (id[i] == -1) {
swap(id[i], id[i + len]);
st.pb(1);
continue;
}
comp(id[i], id[i + len], isy);
}
merge(merge, l, mid, isy);
merge(merge, mid + 1, r, isy);
};
auto undo = [&](auto undo, int l, int r)->void {
if (l == r) return;
int mid = (l + r) / 2, len = mid - l + 1;
undo(undo, mid + 1, r);
undo(undo, l, mid);
for (int i = mid; i >= l; i--) {
if (id[i + len] == -1) {
if (st.back() == 1) swap(id[i], id[i + len]);
} else {
swap_a(id[i], id[i + len], st.back());
}
st.pop_back();
}
};
merge(merge, 0, sz - 1, 0);
int cur = a[id[0]].w;
FOR (i, 1, n + m - 1) {
cur = opf(OP_AND, cur, a[id[i]].t, W_LEN);
a[id[i]].w = ops(OP_OR , cur, a[id[i]].w, W_LEN);
cur = a[id[i]].w;
}
undo(undo, 0, sz - 1);
auto perm = [&](auto perm, int l, int r, int &ptr)->void {
if (l == r) return;
int mid = (l + r) / 2, len = mid - l + 1;
FOR (i, l, mid) if (i + len <= r) swap_a(i, i + len, ptr++);
perm(perm, l, mid, ptr);
perm(perm, mid + 1, r, ptr);
FOR (i, l, mid) if (i + len <= r) swap_a(i, i + len, ptr++);
};
auto add = [&](int x, int y) {
array<int, W_LEN> xy, cr;
cr[1] = op(OP_AND, x, y);
FOR (i, 1, W_LEN - 1) {
xy[i] = op(OP_XOR, x + i, y + i);
if (i < W_LEN - 1) {
int tmp = op(OP_AND, x + i, y + i);
cr[i + 1] = op(OP_AND, xy[i], cr[i] );
cr[i + 1] = op(OP_OR , tmp , cr[i + 1]);
}
}
int s = op(OP_XOR, x, y);
FOR (i, 1, W_LEN - 1) op(OP_XOR, xy[i], cr[i]);
return s;
};
int ptr = la + DS_LEN * m;
perm(perm, n, n + m - 1, ptr);
merge(merge, 0, sz - 1, 1);
cur = opf(OP_ZERO, 0, 0, W_LEN);
FOR (i, 0, n + m - 1) {
a[id[i]].w = opf(OP_AND, a[id[i]].w, a[id[i]].t, W_LEN);
a[id[i]].w = add(cur, a[id[i]].w);
cur = opf(OP_AND, a[id[i]].w, a[id[i]].t, W_LEN);
}
undo(undo, 0, sz - 1);
ptr = DS_LEN * n;
perm(perm, 0, n - 1, ptr);
FOR (i, 0, n - 1) FOR (j, 0, 15) outputs_circuit[i][j] = a[i].w + j;
return lc;
}
Compilation message
abc.cpp: In function 'int conv(const char*)':
abc.cpp:126:1: warning: control reaches end of non-void function [-Wreturn-type]
126 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1244 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1244 KB |
Correct! |
| 2 |
Correct |
3 ms |
1220 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1244 KB |
Correct! |
| 2 |
Correct |
3 ms |
1220 KB |
Correct! |
| 3 |
Correct |
316 ms |
210156 KB |
Correct! |
| 4 |
Correct |
267 ms |
211584 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
6224 KB |
Correct! |
| 2 |
Correct |
161 ms |
106416 KB |
Correct! |
| 3 |
Correct |
187 ms |
137980 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
6224 KB |
Correct! |
| 2 |
Correct |
161 ms |
106416 KB |
Correct! |
| 3 |
Correct |
187 ms |
137980 KB |
Correct! |
| 4 |
Correct |
173 ms |
106784 KB |
Correct! |
| 5 |
Correct |
214 ms |
139080 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
6224 KB |
Correct! |
| 2 |
Correct |
161 ms |
106416 KB |
Correct! |
| 3 |
Correct |
187 ms |
137980 KB |
Correct! |
| 4 |
Correct |
173 ms |
106784 KB |
Correct! |
| 5 |
Correct |
214 ms |
139080 KB |
Correct! |
| 6 |
Correct |
137 ms |
87772 KB |
Correct! |
| 7 |
Correct |
296 ms |
192888 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
552 ms |
366012 KB |
Correct! |
| 2 |
Correct |
534 ms |
364580 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
552 ms |
366012 KB |
Correct! |
| 2 |
Correct |
534 ms |
364580 KB |
Correct! |
| 3 |
Correct |
538 ms |
336524 KB |
Correct! |
| 4 |
Correct |
535 ms |
365060 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1244 KB |
Correct! |
| 2 |
Correct |
3 ms |
1220 KB |
Correct! |
| 3 |
Correct |
316 ms |
210156 KB |
Correct! |
| 4 |
Correct |
267 ms |
211584 KB |
Correct! |
| 5 |
Correct |
12 ms |
6224 KB |
Correct! |
| 6 |
Correct |
161 ms |
106416 KB |
Correct! |
| 7 |
Correct |
187 ms |
137980 KB |
Correct! |
| 8 |
Correct |
173 ms |
106784 KB |
Correct! |
| 9 |
Correct |
214 ms |
139080 KB |
Correct! |
| 10 |
Correct |
137 ms |
87772 KB |
Correct! |
| 11 |
Correct |
296 ms |
192888 KB |
Correct! |
| 12 |
Correct |
552 ms |
366012 KB |
Correct! |
| 13 |
Correct |
534 ms |
364580 KB |
Correct! |
| 14 |
Correct |
538 ms |
336524 KB |
Correct! |
| 15 |
Correct |
535 ms |
365060 KB |
Correct! |
| 16 |
Correct |
568 ms |
369768 KB |
Correct! |
| 17 |
Correct |
569 ms |
372312 KB |
Correct! |
