#include "abc.h"
// #define DEBUG
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<fstream>
using namespace std;
// 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 NUM_LEN = 16, NAME_LEN = 21, OBJ_LEN = 58;
vector<int> deb;
#define FOR_NUM(i) for(int i=0; i<NUM_LEN; i++)
#define FOR_NAME(i) for(int i=0; i<NAME_LEN; i++)
#define all(vec) vec.begin(), vec.end()
#define pii pair<int, int>
#define F first
#define S second
#define mkp make_pair
fstream nothing;
#ifdef DEBUG
#define debug cout
#else
#define debug nothing
#endif
struct stc {
int X, Y, W;
stc(int x=0, int y=0, int w=0): X(x), Y(y), W(w) {}
};
vector<int> Vec;
string Str = "";
void Perm(int l, int r) {
// debug << l << ' ' << r << endl;
if(l >= r) return;
// ===== Init =====
int n = r-l+1, len = (n+1)/2;
int arr[len]; fill(arr, arr+len, 0);
// ===== Change 1 =====
vector<bool> change(len, 0);
while(1) {
int a = -1, b = -1;
for(int i=l; i<l+len; i++) {
for(int j=i+1; j<l+len; j++) {
if(Vec[i]%len == Vec[j]%len) {
a = i, b = j;
break;
}
}
if(a != -1) break;
}
if(a == -1) break;
while(1) {
if(b == l+len-1 && n%2 == 1) swap(a, b);
int c = -1;
for(int i=l; i<l+len; i++) {
if(i != b && Vec[i]%len == Vec[b+len]%len) {
c = i;
break;
}
}
change[b-l] = !change[b-l];
swap(Vec[b], Vec[b+len]);
if(c == -1) break;
a = b, b = c;
}
}
for(int i=0; i<len; i++) Str += (char)('0'+change[i]);
// ===== Recursion =====
int mp[len];
for(int i=l; i<l+len; i++) {
int num = Vec[i]%len;
mp[num] = Vec[i];
Vec[i] = num;
}
Perm(l, l+len-1);
for(int i=l; i<l+len; i++) Vec[i] = mp[Vec[i]];
for(int i=l+len; i<=r; i++) {
int num = Vec[i]%len;
mp[num] = Vec[i];
Vec[i] = num;
}
Perm(l+len, r);
for(int i=l+len; i<=r; i++) Vec[i] = mp[Vec[i]];
// ===== Change 2 =====
for(int i=l; i<l+len; i++) {
if(i+len > r) {
Str += '0';
continue;
}
if(Vec[i] > Vec[i+len]) {
Str += '1';
swap(Vec[i], Vec[i+len]);
}
else Str += '0';
}
}
// Alice
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs_alice[]
) {
// =============== Convert to Object ===============
vector<stc> vec(n);
for(int i=0; i<n; i++) {
int name=0, num=numbers[i];
string str = names[i];
while(str.length() != 4) str += (char)('a'-1);
for(auto &j : str) name = name*27+(j-'a'+1);
vec[i] = stc(name, name, num);
}
// debug << " Convert to Object " << endl;
// =============== Get Pemutation of Ydown -> Init ===============
vector<int> sorted(n), perm(n);
for(int i=0; i<n; i++) sorted[i] = vec[i].Y;
sort(all(sorted), greater<int>());
map<int, int> mp;
for(int i=0; i<n; i++) mp[vec[i].Y] = i;
for(int i=0; i<n; i++) perm[i] = mp[sorted[i]];
string Ydown_Init = "";
// for(int i=0; i<n; i++) debug << perm[i] << ' ';
// debug << endl;
Vec = perm, Str.clear();
Perm(0, n-1);
Ydown_Init = Str;
// debug << Ydown_Init << endl;
// debug << "Get Pemutation of Ydown -> Init" << endl;
// =============== Sort vec and Pass Data to Circuit (Xup + Ydown_Init) ===============
sort(vec.begin(), vec.end(), [&](stc a, stc b) {return a.X < b.X;});
int cur=0;
for(int i=0; i<n; i++) {
outputs_alice[cur++] = 0;
for(int j=0; j<NAME_LEN-1; j++)
outputs_alice[cur++] = (vec[i].X >> j) & 1;
outputs_alice[cur++] = 1;
for(int j=0; j<NAME_LEN-1; j++)
outputs_alice[cur++] = (vec[i].Y >> j) & 1;
FOR_NUM(j)
outputs_alice[cur++] = (vec[i].W >> j) & 1;
}
for(int i=0; i<(int)Ydown_Init.length(); i++) outputs_alice[cur++] = Ydown_Init[i] - '0';
while(cur != 69*n) outputs_alice[cur++] = 0;
// debug << "Sort vec and Pass Data to Circuit (Xup + Ydown_Init)" << endl;
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[]
) {
// =============== Convert to Object ===============
vector<pair<pii, int> > sorted(m);
for(int i=0; i<m; i++) {
int s=0, r=0;
string S = senders[i], R = recipients[i];
while(S.length() != 4) S += (char)('a'-1);
while(R.length() != 4) R += (char)('a'-1);
for(auto &j : S) s = s*27+(j-'a'+1);
for(auto &j : R) r = r*27+(j-'a'+1);
sorted[i].F = make_pair(s, r);
}
// =============== Get Pemutation of Xdown -> Yup ===============
vector<int> perm(m);
sort(all(sorted), [&](pair<pii, int> a, pair<pii, int> b) {if(a.F.S != b.F.S) return a.F.S < b.F.S; return a.F.F < b.F.F;});
for(int i=0; i<m; i++) sorted[i].S = i;
sort(all(sorted), [&](pair<pii, int> a, pair<pii, int> b) {if(a.F.F != b.F.F) return a.F.F > b.F.F; return a.F.S > b.F.S;});
for(int i=0; i<m; i++) perm[i] = sorted[i].S;
// for(int i=0; i<m; i++) debug << perm[i] << ' ';
// debug << " !!!!! " << endl;
string Xdown_Yup = "";
Vec = perm, Str.clear();
Perm(0, m-1);
Xdown_Yup = Str;
// debug << Xdown_Yup << " ???" << endl;
// =============== Pass Data to Circuit (Xdown + Xdown_Yup) ===============
int cur=0;
for(int i=0; i<m; i++) {
outputs_bob[cur++] = 1;
for(int j=0; j<NAME_LEN-1; j++)
outputs_bob[cur++] = (sorted[i].F.F >> j) & 1;
outputs_bob[cur++] = 0;
for(int j=0; j<NAME_LEN-1; j++)
outputs_bob[cur++] = (sorted[i].F.S >> j) & 1;
FOR_NUM(j)
outputs_bob[cur++] = 0;
}
// debug << Xdown_Yup << " ??? " << endl;
for(int i=0; i<(int)Xdown_Yup.length(); i++) outputs_bob[cur++] = Xdown_Yup[i] - '0';
while(cur != 69*m) outputs_bob[cur++] = 0;
return cur;
}
// 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 cur = la + lb;
// =============== Initialization ===============
auto op = [&](int o, int a, int b) {
operations[cur] = o;
operands[cur][0] = a, operands[cur][1] = b;
return cur ++ ;
};
int zero = op(OP_ZERO, 0, 0);
int one = op(OP_ONE, 1, 1);
int ZERO = cur;
FOR_NUM(i) op(OP_ZERO, 0, 0);
int ZERO_NAME = cur;
FOR_NAME(i) op(OP_ZERO, 0, 0);
int INF = cur;
FOR_NUM(i) op(OP_ONE, 1, 1);
int INF_NAME = cur;
FOR_NAME(i) op(OP_ONE, 1, 1);
auto ADD = [&](int a, int b) {
vector<int> carry = {zero}, digit;
FOR_NUM(i) {
int d = op(OP_XOR, a+i, b+i);
int c1 = op(OP_AND, a+i, b+i);
int c2 = op(OP_AND, d, carry[i]);
if(i != NUM_LEN-1) carry.push_back(op(OP_OR, c1, c2));
digit.push_back(d);
}
int ret = cur;
FOR_NUM(i) op(OP_XOR, digit[i], carry[i]);
return ret;
};
// ================ Solve ===============
int n = la/69, m = lb/69;
int SIZE = 1;
while(SIZE < n+m) SIZE *= 2;
vector<vector<int> > arr(3, vector<int>(SIZE)); // 0 = X, 1 = Y, 2 = W;
for(int i=0; i<n; i++) {
arr[0][i] = OBJ_LEN*i;
arr[1][i] = arr[0][i] + NAME_LEN;
arr[2][i] = arr[1][i] + NAME_LEN;
}
for(int i=0; i<m; i++) {
arr[0][SIZE-m+i] = la+OBJ_LEN*i;
arr[1][SIZE-m+i] = arr[0][SIZE-m+i] + NAME_LEN;
arr[2][SIZE-m+i] = arr[1][SIZE-m+i] + NAME_LEN;
}
for(int i=n; i<SIZE-m; i++) {
arr[0][i] = INF_NAME;
arr[1][i] = INF_NAME;
arr[2][i] = INF;
}
// ===== Add Numbers to Letters =====
vector<int> signals;
auto swap = [&](int a, int b, int s) {
vector<int> veca[3], vecb[3];
for(int j=0; j<3; j++) {
int len = (j == 2 ? NUM_LEN : NAME_LEN);
for(int i=0; i<len; i++) {
int p = arr[j][a]+i, q = arr[j][b]+i;
int ns = op(OP_NOT_X0, s, 0);
veca[j].push_back(op(OP_OR, op(OP_AND, p, ns), op(OP_AND, q, s)));
int num = veca[j].back();
vecb[j].push_back(op(OP_XOR, op(OP_XOR, num, p), q));
}
}
for(int i=0; i<3; i++) {
int aa = cur; for(auto &j : veca[i]) op(OP_OR, j, 0);
int bb = cur; for(auto &j : vecb[i]) op(OP_OR, j, 0);
arr[i][a] = aa;
arr[i][b] = bb;
}
};
auto cmp = [&](int a, int b, int k) {
int s = zero;
int P = arr[k][a], Q = arr[k][b];
if(Q == INF) {
signals.push_back(zero);
return;
}
if(P == INF) {
signals.push_back(one);
swap(a, b, one);
return;
}
FOR_NAME(i) {
int p = P+i, q = Q+i;
int eq = op(OP_EQUAL, p, q), num = op(OP_AND, p, op(OP_NOT_X0, q, q));
s = op(OP_OR, op(OP_AND, s, eq), num);
}
signals.push_back(s);
swap(a, b, s);
};
auto merge = [&](auto merge1, int l, int r, int k) {
// if(l != 0 || r != n+m-1) return;
if(l >= r) return;
int m = (l+r)>>1, len = m-l+1;
for(int i=l; i<=m; i++) cmp(i, i+len, k);
merge1(merge1, l, m, k); merge1(merge1, m+1, r, k);
};
merge(merge, 0, SIZE-1, 0);
// deb = signals;
int num = ZERO;
for(int i=0; i<n+m; i++) {
int tmp = cur;
FOR_NUM(j) op(OP_AND, num+j, arr[0][i]);
int pos = cur;
FOR_NUM(j) op(OP_OR, tmp+j, arr[2][i]+j);
arr[2][i] = pos;
num = arr[2][i];
}
/**/ debug << "Add Numbers to Letters Complete" << endl;
// ===== Unmerge =====
// for(auto &i : signals) debug << i << ' ';
// debug << endl;
reverse(all(signals));
int p=0;
auto unmerge = [&](auto unmerge1, int l, int r) {
if(l >= r) return;
int m = (l+r)>>1, len = m-l+1;
unmerge1(unmerge1, m+1, r); unmerge1(unmerge1, l, m);
for(int i=m; i>=l; i--) {
// debug << i << ' ' << i+len << ' ' << signals[p] << " ???" << endl;
if(i+len <= r) swap(i, i+len, signals[p]);
p++;
}
};
unmerge(unmerge, 0, SIZE-1);
/*
for(int i=0; i<SIZE; i++) {
deb.push_back(arr[0][i]);
deb.push_back(arr[1][i]);
deb.push_back(arr[2][i]);
}
*/
/**/ debug << "Unmerge Complete" << endl;
// ===== Change Permutation =====
int perm = la + OBJ_LEN*m;
p=0;
auto applyperm = [&](auto applyperm1, int l, int r) {
if(l >= r) return;
int num = r-l+1, len = (num+1)/2;
// ===== Change 1 =====
for(int i=l; i<l+len; i++) {
if(i+len <= r)
swap(i, i+len, perm+p);
p++;
}
// ===== Recursion =====
applyperm1(applyperm1, l, l+len-1);
applyperm1(applyperm1, l+len, r);
// ===== Change 2 =====
for(int i=l; i<l+len; i++) {
if(i+len <= r)
swap(i, i+len, perm+p);
p++;
}
};
applyperm(applyperm, SIZE-m, SIZE-1);
auto arr2 = arr;
for(int i=0; i<m; i++)
for(int j=0; j<3; j++)
arr[j][i] = arr2[j][SIZE-m+i];
for(int i=0; i<SIZE-n-m; i++)
for(int j=0; j<3; j++)
arr[j][m+i] = arr2[j][n+i];
for(int i=0; i<n; i++)
for(int j=0; j<3; j++)
arr[j][SIZE-n+i] = arr2[j][n-1-i];
/**/ debug << "Change Permutation Complete" << endl;
// ===== Add Number to Person =====
signals.clear();
merge(merge, 0, SIZE-1, 1);
num = ZERO;
for(int i=0; i<n+m; i++) {
int t = arr[1][i], nt = op(OP_NOT_X0, t, 0);
// debug << t << ' ' << nt << " ???" << endl;
int reset = cur;
FOR_NUM(j) op(OP_AND, arr[2][i]+j, nt);
arr[2][i] = reset;
int num2 = cur;
FOR_NUM(j) op(OP_AND, num+j, t);
arr[2][i] = ADD(arr[2][i], num2);
int tmp = cur;
FOR_NUM(j) op(OP_AND, arr[2][i]+j, nt);
num = ADD(num, tmp);
int num3 = cur;
FOR_NUM(j) op(OP_AND, num+j, nt);
num = num3;
}
/*
for(int i=0; i<SIZE; i++) {
deb.push_back(arr[0][i]);
deb.push_back(arr[1][i]);
deb.push_back(arr[2][i]);
}
*/
// deb = signals;
/**/ debug << "Add Number to Person Complete" << endl;
// ===== Unmerge =====
reverse(all(signals));
p=0;
unmerge(unmerge, 0, SIZE-1);
/**/ debug << "Unmerge Complete" << endl;
// ===== Change Permutation =====
perm = OBJ_LEN*n;
p=0;
applyperm(applyperm, SIZE-n, SIZE-1);
/**/ debug << "Change Permutation Complete" << endl;
// ===== Output Answer =====
for(int i=0; i<n; i++) {
int ans = arr[2][SIZE-n+i];
FOR_NUM(j) outputs_circuit[i][j] = ans + j;
}
/**/ debug << "Solve Complete" << endl;
return cur;
}
/*
for(int i=0; i<n+m; i++) {
deb.push_back(arr[0][i]);
deb.push_back(arr[1][i]);
deb.push_back(arr[2][i]);
}
*/
Compilation message
abc.cpp: In function 'int circuit(int, int, int*, int (*)[2], int (*)[16])':
abc.cpp:253:7: warning: unused variable 'ZERO_NAME' [-Wunused-variable]
253 | int ZERO_NAME = cur;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1276 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1276 KB |
Correct! |
| 2 |
Correct |
2 ms |
1284 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1276 KB |
Correct! |
| 2 |
Correct |
2 ms |
1284 KB |
Correct! |
| 3 |
Correct |
461 ms |
327516 KB |
Correct! |
| 4 |
Correct |
451 ms |
328640 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
14828 KB |
Correct! |
| 2 |
Correct |
800 ms |
269052 KB |
Correct! |
| 3 |
Incorrect |
43 ms |
1520 KB |
TLE bob() exceeds time limit |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
14828 KB |
Correct! |
| 2 |
Correct |
800 ms |
269052 KB |
Correct! |
| 3 |
Incorrect |
43 ms |
1520 KB |
TLE bob() exceeds time limit |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
14828 KB |
Correct! |
| 2 |
Correct |
800 ms |
269052 KB |
Correct! |
| 3 |
Incorrect |
43 ms |
1520 KB |
TLE bob() exceeds time limit |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
13448 KB |
TLE bob() exceeds time limit |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
13448 KB |
TLE bob() exceeds time limit |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1276 KB |
Correct! |
| 2 |
Correct |
2 ms |
1284 KB |
Correct! |
| 3 |
Correct |
461 ms |
327516 KB |
Correct! |
| 4 |
Correct |
451 ms |
328640 KB |
Correct! |
| 5 |
Correct |
19 ms |
14828 KB |
Correct! |
| 6 |
Correct |
800 ms |
269052 KB |
Correct! |
| 7 |
Incorrect |
43 ms |
1520 KB |
TLE bob() exceeds time limit |
| 8 |
Halted |
0 ms |
0 KB |
- |
