(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #931920

#TimeUsernameProblemLanguageResultExecution timeMemory
931920becaidoAlice, Bob, and Circuit (APIO23_abc)C++17
100 / 100
558 ms370044 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> #include "abc.h" using namespace std; #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back const int OP_ZERO = 0; const int OP_NOR = 1; const int OP_GREATER = 2; const int OP_NOT_X1 = 3; const int OP_LESS = 4; const int OP_NOT_X0 = 5; const int OP_XOR = 6; const int OP_NAND = 7; const int OP_AND = 8; const int OP_EQUAL = 9; const int OP_X0 = 10; const int OP_GEQ = 11; const int OP_X1 = 12; const int OP_LEQ = 13; const int OP_OR = 14; const int OP_ONE = 15; 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; } 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; } 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; } 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 (stderr)

abc.cpp: In function 'int conv(const char*)':
abc.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...