#include "abc.h"
#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;
#define DEBUG
#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) {}
};
void Perm(vector<int> &vec, int l, int r, string &str) {
// ===== Init =====
int n = r-l+1, len = (n+1)/2;
int arr[len]; fill(arr, arr+len, 0);
if(l == r) return;
// ===== 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) {
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(vec, l, l+len-1, str);
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(vec, l+len, r, str);
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);
}
// =============== 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;
Perm(perm, 0, n-1, Ydown_Init);
// debug << 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<Ydown_Init.length(); i++) outputs_alice[cur++] = Ydown_Init[i] - '0';
while(cur != 69*n) outputs_alice[cur++] = 0;
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<stc> vec(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);
vec[i] = stc(s, r, 0);
}
// =============== Get Pemutation of Xdown -> Yup ===============
vector<pii> sortX(m), sortY(m);
vector<int> perm(m);
for(int i=0; i<m; i++) sortX[i] = mkp(vec[i].X, vec[i].Y);
sortY = sortX;
sort(all(sortX), [&](pii a, pii b) {if(a.F != b.F) return a.F > b.F; return a.S > b.S;});
sort(all(sortY), [&](pii a, pii b) {if(a.S != b.S) return a.S < b.S; return a.F < b.F;});
map<pii, vector<int> > mp;
for(int i=0; i<m; i++) mp[sortY[i]].push_back(i);
for(auto &i : mp) i.S.push_back(0);
for(int i=0; i<m; i++) perm[i] = mp[sortX[i]][mp[sortX[i]].back()++];
// for(int i=0; i<m; i++) debug << perm[i] << ' ';
// debug << endl;
string Xdown_Yup = "";
Perm(perm, 0, m-1, Xdown_Yup);
/*
for(int i=0; i<m; i++) debug << sortX[i].F << ' ';
debug << endl;
for(int i=0; i<m; i++) debug << sortX[i].S << ' ';
debug << endl << endl;
for(int i=0; i<m; i++) debug << sortY[i].F << ' ';
debug << endl;
for(int i=0; i<m; i++) debug << sortY[i].S << ' ';
debug << endl << endl;
*/
// 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++] = (sortX[i].F >> j) & 1;
outputs_bob[cur++] = 0;
for(int j=0; j<NAME_LEN-1; j++)
outputs_bob[cur++] = (sortX[i].S >> j) & 1;
FOR_NUM(j)
outputs_bob[cur++] = 0;
}
// debug << Xdown_Yup.length() << " ??? " << endl;
for(int i=0; i<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 ZERO = cur;
FOR_NUM(i) op(OP_ZERO, 0, 0);
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;
vector<vector<int> > arr(3, vector<int>(n+m)); // 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][n+i] = la+OBJ_LEN*i;
arr[1][n+i] = arr[0][n+i] + NAME_LEN;
arr[2][n+i] = arr[1][n+i] + NAME_LEN;
}
// ===== Add Numbers to Letters =====
vector<int> signals;
auto swap = [&](int a, int b, int s) {
vector<int> veca[3], vecb[3];
FOR_NAME(i) {
for(int j=0; j<3; j++) {
int p = arr[j][a]+i, q = arr[j][b]+i;
// debug << q << ' ' << b << " ???" << endl;
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;
FOR_NAME(i) {
int p = arr[k][a]+i, q = arr[k][b]+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, n+m-1, 0);
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];
// deb.push_back(arr[0][i]);
// deb.push_back(arr[1][i]);
// deb.push_back(arr[2][i]);
}
// ===== Unmerge =====
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;
swap(i, i+len, signals[p++]);
}
};
unmerge(unmerge, 0, n+m-1);
// ===== Change Permutation =====
int perm = la + OBJ_LEN*m;
p=0;
auto calc = [&](auto calc1, int l, int r) {
if(l == r) return;
int n = r-l+1, len = (n+1)/2;
for(int i=l+len-1; i>=l; i--) p++;
calc1(calc1, l+len, r);
calc1(calc1, l, l+len-1);
for(int i=l+len-1; i>=l; i--) p++;
};
auto applyperm = [&](auto applyperm1, int l, int r) {
if(l == r) return;
int num = r-l+1, len = (num+1)/2;
// ===== Change 2 =====
for(int i=l+len-1; i>=l; i--) {
if(i+len <= r)
swap(i, i+len, perm+p);
p--;
}
// ===== Recursion =====
applyperm1(applyperm1, l+len, r);
applyperm1(applyperm1, l, l+len-1);
// ===== Change 1 =====
for(int i=l+len-1; i>=l; i--) {
if(i+len <= r)
swap(i, i+len, perm+p);
p--;
}
};
calc(calc, n, n+m-1); p -- ;
applyperm(applyperm, n, n+m-1);
auto arr2 = arr;
for(int i=0; i<m; i++)
for(int j=0; j<3; j++)
arr[j][i] = arr2[j][n+i];
for(int i=0; i<n; i++)
for(int j=0; j<3; j++)
arr[j][m+i] = arr2[j][n-1-i];
/*
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]);
}
*/
// ===== Add Number to Person =====
signals.clear();
merge(merge, 0, n+m-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;
}
// ===== Unmerge =====
reverse(all(signals));
p=0;
unmerge(unmerge, 0, n+m-1);
/*
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]);
}
*/
// ===== Change Permutation =====
perm = OBJ_LEN*n;
p=0;
calc(calc, m, n+m-1); p -- ;
applyperm(applyperm, m, n+m-1);
// ===== Output Answer =====
for(int i=0; i<n; i++) {
int ans = arr[2][m+i];
FOR_NUM(j) outputs_circuit[i][j] = ans + j;
}
return cur;
}
/*
s = (s & eq) | num
s = 0 --> aa = a
(a & !s) | (b & s);
*/
Compilation message
abc.cpp: In function 'int alice(int, const char (*)[5], const short unsigned int*, bool*)':
abc.cpp:165:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for(int i=0; i<Ydown_Init.length(); i++) outputs_alice[cur++] = Ydown_Init[i] - '0';
| ~^~~~~~~~~~~~~~~~~~~~
abc.cpp: In function 'int bob(int, const char (*)[5], const char (*)[5], bool*)':
abc.cpp:232:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
232 | for(int i=0; i<Xdown_Yup.length(); i++) outputs_bob[cur++] = Xdown_Yup[i] - '0';
| ~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1281 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1281 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1281 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10038 ms |
600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10038 ms |
600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1281 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
