#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
#define vi vector<int>
// 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;
const int NAME_LEN = 19;
const int OBJ_LEN = NUM_LEN+NAME_LEN*2+1;
//vector<int> OUT;
// Alice
namespace PERM{
string code;
void encode(vector<int> v){
if(v.size() == 1)return;
int n = v.size();
if(n&1){
v.push_back(n);
n++;
}
vector<int> pos(n,-1);
for(int i = 0;i<n;i++)pos[v[i]] = i;
for(auto &i:pos)assert(i>=0);
int m = n>>1;
auto dual = [&](int k){assert(0<=k&&k<n);return k<m?k+m:k-m;};
auto same = [&](int a,int b)->bool{return (a<m&&b<m)||(a>=m&&b>=m);};
string flip(m,'0');
bool done[n] = {};
for(int i = 0;i<n;i++){
if(done[i]||!same(i,pos[dual(v[i])]))continue;
int now = i;
vector<int> cyc;
cyc.push_back(now);
do{
done[now] = true;
now = pos[dual(v[now])];
cyc.push_back(now);
done[now] = true;
now = dual(now);
cyc.push_back(now);
}while(!done[now]);
vector<int> tags;
for(int i = 1;i<cyc.size();i++){
if(same(cyc[i],cyc[i-1]))tags.push_back(i);
}
assert(tags.size()%2 == 0);
for(int i = 1;i<tags.size();i+=2){
for(int j = tags[i-1];j<tags[i];j++){
flip[cyc[j]%m] = '1';
}
}
}
code += flip;
vector<int> lv,rv;
for(int i = 0;i<m;i++){
if(flip[i] == '1'){
swap(v[i],v[i+m]);
}
}
for(int i = 0;i<m;i++){
lv.push_back(v[i]%m);rv.push_back(v[dual(i)]%m);
}
encode(lv);
encode(rv);
flip = string(m,'0');
sort(v.begin(),v.begin()+m,[&](int a,int b){return a%m<b%m;});
sort(v.begin()+m,v.end(),[&](int a,int b){return a%m<b%m;});
for(int i = 0;i<m;i++){
if(v[i]>v[i+m])flip[i] = '1';
}
code += flip;
return;
}
}
function<int(string)> Hash = [](string s){
int re = 0;
int ts = 1;
for(int i = 1;i<=4;i++){
ts *= 26;
if(s.size()>i)re += ts;
}
ts = 1;
for(auto &i:s){
re += ts*(i-'a'+1);
ts *= 26;
}
assert(__lg(re)<NAME_LEN);
return re;
};
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs_alice[]
) {
cerr<<"alice in!"<<endl;
vector<pii> v;
for(int i = 0;i<n;i++){
v.push_back(pii(Hash(string(names[i])),i));
}
sort(v.begin(),v.end());
for(auto &i:v)cerr<<i.fs<<',';cerr<<endl;
vector<int> perm;
for(auto &i:v)perm.push_back(i.sc);
PERM::code.clear();
PERM::encode(perm);
auto code = PERM::code;
int ptr = 0;
cerr<<"PERM:";for(auto &i:perm)cerr<<i<<',';cerr<<endl;
for(int i = 0;i<n;i++){
int id = v[i].sc;
for(int j = 0;j<NAME_LEN;j++){
outputs_alice[ptr++] = (v[i].fs>>j)&1;
}
for(int j = 0;j<NAME_LEN;j++){
outputs_alice[ptr++] = (v[i].fs>>j)&1;
}
outputs_alice[ptr++] = 0;
for(int j = 0;j<NUM_LEN;j++){
outputs_alice[ptr++] = (numbers[id]>>j)&1;
}
}
for(auto &i:code){
outputs_alice[ptr++] = (i=='0'?0:1);
}
cerr<<"la = "<<ptr<<','<<n*OBJ_LEN<<','<<code.size()<<endl;
cerr<<code<<endl;
for(int i = 0;i<ptr;i++)cout<<outputs_alice[i];cout<<endl;
cerr<<"alice out!"<<endl;
return ptr;
}
// Bob
int // returns lb
bob(
/* in */ const int m,
/* in */ const char senders[][5],
/* in */ const char recipients[][5],
/* out */ bool outputs_bob[]
) {
cerr<<"bob in!"<<endl;
int ptr = 0;
vector<pii> v;
for(int i = 0;i<m;i++)v.push_back(pii(Hash(string(senders[i])),Hash(string(recipients[i]))));
sort(v.begin(),v.end(),[](pii a,pii b){return a.sc>b.sc;});
for(auto &i:v)cerr<<i.fs<<','<<i.sc<<endl;cerr<<endl;
vector<int> perm;
for(int i = 0;i<m;i++)perm.push_back(i);
sort(perm.begin(),perm.end(),[&](int a,int b){return v[a].fs>v[b].fs;});
auto tv = v;
for(int i = 0;i<m;i++)tv[i] = v[perm[i]];
v = tv;
PERM::code.clear();
PERM::encode(perm);
auto code = PERM::code;
for(int i = 0;i<m;i++){
for(int j = 0;j<NAME_LEN;j++){
outputs_bob[ptr++] = (v[i].fs>>j)&1;
}
for(int j = 0;j<NAME_LEN;j++){
outputs_bob[ptr++] = (v[i].sc>>j)&1;
}
outputs_bob[ptr++] = 1;
for(int j = 0;j<NUM_LEN;j++){
outputs_bob[ptr++] = 0;
}
}
for(int i = 0;i<code.size();i++){
outputs_bob[ptr++] = (code[i] == '0'?0:1);
}
for(int i = 0;i<ptr;i++)cout<<outputs_bob[i];cout<<endl;
cerr<<"bob out!"<<endl;
return ptr;
}
int zero,one;
struct Obj{
int name1,name2,val;
int tp;//pointer to type
Obj(){
name1 = name2 = val = tp = zero;
}
Obj(int a){
name1 = a,name2 = a+NAME_LEN,tp = a+NAME_LEN*2,val = a+NAME_LEN*2+1;
}
};
const int B = 2048;
// 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]
) {
cerr<<"circuit in!"<<endl;
int ptr = la+lb;
function<int(int ,int ,int)> addop = [&](int a,int b,int op){
//cerr<<"addop#"<<setw(7)<<ptr<<endl;
assert(ptr<20000000);
operands[ptr][0] = a,operands[ptr][1] = b;
operations[ptr] = op;
return ptr++;
};
function<pii(int,int)> HALF_ADDER = [&](int a,int b){//{val,carry}
pii re;
re.fs = addop(a,b,OP_XOR);
re.sc = addop(a,b,OP_AND);
return re;
};
function<int(int,int)> FULL_ADDER = [&](int a,int b){//adds a,b and returns c
vector<pii> re;
int car = zero;
for(int i = 0;i<NUM_LEN;i++){
auto [t1,t2] = HALF_ADDER(a+i,b+i);
re.push_back(pii(t1,car));
car = addop(t1,car,OP_AND);
car = addop(car,t2,OP_OR);
}
int head = ptr;
for(auto &i:re){
addop(i.fs,i.sc,OP_XOR);
}
return head;
};
function<int(vi,vi)> LESS = [&](vi a,vi b){//size-1 ~ 0,a<b?1:0
auto flag = zero,tag = zero;
assert(a.size() == b.size()&&a.size());
for(auto &i:a)assert(i>=0&&i<ptr);
for(auto &i:b)assert(i>=0&&i<ptr);
for(int i = a.size()-1;i>=0;i--){
int tmp = addop(a[i],b[i],OP_LESS);
tmp = addop(flag,tmp,OP_LESS);
tag = addop(tag,tmp,OP_OR);
tmp = addop(a[i],b[i],OP_XOR);
flag = addop(flag,tmp,OP_OR);
}
return tag;
};
auto SWAPIF = [&](Obj& oa,Obj& ob,int f){
vi pa,pb;
vector<pii> va,vb;
for(int i = 0;i<NAME_LEN;i++){
pa.push_back(oa.name1+i);
pb.push_back(ob.name1+i);
}
for(int i = 0;i<NAME_LEN;i++){
pa.push_back(oa.name2+i);
pb.push_back(ob.name2+i);
}
pa.push_back(oa.tp);
pb.push_back(ob.tp);
for(int i = 0;i<NUM_LEN;i++){
pa.push_back(oa.val+i);
pb.push_back(ob.val+i);
}
assert(pa.size() == OBJ_LEN&&pb.size() == OBJ_LEN);
for(int i = 0;i<pa.size();i++){//va:OP_OR;vb:OP_XOR
int ta = pa[i],tb = pb[i];
int t1 = addop(f,ta,OP_LESS);
int t2 = addop(f,tb,OP_AND);
va.push_back(pii(t1,t2));
int xorsum = addop(ta,tb,OP_XOR);
vb.push_back(pii(xorsum,-1));
}
oa.name1 = ptr,oa.name2 = ptr+NAME_LEN,oa.tp = ptr+NAME_LEN*2,oa.val = ptr+NAME_LEN*2+1;
for(auto &i:va)addop(i.fs,i.sc,OP_OR);
ob.name1 = ptr,ob.name2 = ptr+NAME_LEN,ob.tp = ptr+NAME_LEN*2,ob.val = ptr+NAME_LEN*2+1;
for(int i = 0;i<vb.size();i++)addop(vb[i].fs,oa.name1+i,OP_XOR);
assert(va.size() == OBJ_LEN&&vb.size() == OBJ_LEN);
return;
};
vector<vi> done;
function<void(int,int,vector<Obj>&,bool)> bitonic_merge;
bitonic_merge = [&](int l,int r,vector<Obj>& v,bool f)->void{
if(l == r)return;
int len = (r-l+1);
assert((1<<__lg(len)) == len);
len>>=1;
int mid = (l+r)>>1;
for(int i = l;i<=mid;i++){
int flag;
vi va,vb;
if(!f){
va.push_back(v[i+len].tp);for(int j = 0;j<NAME_LEN;j++)va.push_back(v[i+len].name1+j);
vb.push_back(v[i].tp);for(int j = 0;j<NAME_LEN;j++)vb.push_back(v[i].name1+j);
}
else{
va.push_back(v[i+len].tp);for(int j = 0;j<NAME_LEN;j++)va.push_back(v[i+len].name2+j);
vb.push_back(v[i].tp);for(int j = 0;j<NAME_LEN;j++)vb.push_back(v[i].name2+j);
}
flag = LESS(va,vb);
done.push_back(vi({i,i+len,flag}));
SWAPIF(v[i],v[i+len],flag);
}
bitonic_merge(l,mid,v,f);
bitonic_merge(mid+1,r,v,f);
return;
};
/*function<void(vector<Obj>&)>*/auto undo_bitonic = [&](vector<Obj> &v)->void{
cerr<<"UNDO IN!"<<endl;
cerr<<done.size()<<endl;
int C = 0;
while(!done.empty()){
auto a = done.back()[0],b = done.back()[1],f = done.back()[2];
done.pop_back();
assert(0<=a&&a<v.size()&&0<=b&&b<v.size());
SWAPIF(v[a],v[b],f);
}
cerr<<"UNDO OUT!"<<endl;
return;
};
queue<int> q;
function<int()> getcode = [&](){
assert(!q.empty());
auto re = q.front();
q.pop();
return re;
};
function<void(int,int,vector<Obj>&)> apply_perm;
apply_perm = [&](int n,int l,vector<Obj> &v){
if(n == 1)return;
if(n&1)n++;
int m = n>>1;
for(int i = 0;i<m;i++){
while(v.size()<=l+m+i)v.push_back(Obj());
int c = getcode();
SWAPIF(v[l+i],v[l+m+i],c);
}
apply_perm(m,l,v);
apply_perm(m,l+m,v);
for(int i = 0;i<m;i++){
int c = getcode();
SWAPIF(v[l+i],v[l+m+i],c);
}
return;
};
function<void(vector<Obj>&)> SWEEP1 = [&](vector<Obj> &v){
cerr<<"SWEEP1 IN!"<<endl;
int x = zero;
for(auto &i:v){
vector<pii> vv,xv;
for(int j = 0;j<NUM_LEN;j++){
int t1 = addop(i.tp,x+j,OP_AND);
int t2 = addop(i.tp,i.val+j,OP_LESS);
vv.push_back(pii(t1,t2));
xv.push_back(pii(t1,t2));
}
i.val = ptr;
for(auto &i:vv)addop(i.fs,i.sc,OP_OR);
x = ptr;
for(auto &i:xv)addop(i.fs,i.sc,OP_OR);
}
cerr<<"SWEEP1 OUT!"<<endl;
return;
};
function<void(vector<Obj>&)> SWEEP2 = [&](vector<Obj> &v){
cerr<<"SWEEP2 IN!"<<endl;
int x = zero;
int C = 0;
for(auto &i:v){
int sum = FULL_ADDER(x,i.val);
vector<pii> vv,xv;//vv:OP_OR;xv:OP_LESS
for(int j = 0;j<NUM_LEN;j++){
int t1 = addop(i.tp,x+j,OP_AND);
int t2 = addop(i.tp,i.val+j,OP_LESS);
vv.push_back(pii(t1,t2));
xv.push_back(pii(i.tp,sum+j));
}
i.val = ptr;
for(auto &i:vv)addop(i.fs,i.sc,OP_OR);
x = ptr;
for(auto &i:xv)addop(i.fs,i.sc,OP_LESS);
}
cerr<<"SWEEP2 OUT!"<<endl;
return;
};
cerr<<"circuit in!"<<endl;
vector<int> codedp(1010,0);
codedp[1] = 0;
for(int i = 2;i<1010;i++)codedp[i] = codedp[(i+1)>>1]*2+(i+1)/2*2;
cerr<<"DP done!"<<endl;
int n,m;
cerr<<"len = 3:"<<codedp[3]<<endl;
for(n = 1;n*OBJ_LEN+codedp[n] < la;n++);
for(m = 1;m*OBJ_LEN+codedp[m] < lb;m++);
cerr<<"n = "<<n<<endl;
cerr<<"m = "<<m<<endl;
zero = ptr;
for(int i = 0;i<20;i++)addop(0,0,OP_ZERO);
one = addop(0,0,OP_ONE);
cerr<<"zero,one added"<<endl;
vector<Obj> lv,rv,v;
for(int i = 0;i<n;i++)lv.push_back(Obj(i*OBJ_LEN));
for(int i = 0;i<m;i++)rv.push_back(Obj(la+i*OBJ_LEN));
v.clear();
for(auto &i:lv)v.push_back(i);
for(auto &i:rv)v.push_back(i);
while(v.size() != B)v.push_back(Obj());
cerr<<"variable initialized"<<endl;
bitonic_merge(0,v.size()-1,v,0);
cerr<<"ptr = "<<ptr<<endl;
cerr<<"bitonic1"<<endl;
vector<Obj> vv;
for(int i = B-n-m;i<B;i++)vv.push_back(v[i]);
SWEEP1(vv);
for(int i = 0;i<vv.size();i++)v.end()[-1-i] = vv.end()[-1-i];
cerr<<"sweep1"<<endl;
undo_bitonic(v);
cerr<<"undo"<<endl;
for(int i = 0;i<n;i++)lv[i] = v[i];
for(int i = 0;i<m;i++)rv[i] = v[i+n];
for(int i = la+m*OBJ_LEN;i<la+lb;i++)q.push(i);
cerr<<"apply bob"<<endl;
apply_perm(m,0,rv);
rv.resize(m);
assert(q.empty());
v.clear();
for(int i = 0;i<n;i++){
lv[i].tp = addop(one,one,OP_ONE);
}
for(int i = 0;i<m;i++){
rv[i].tp = addop(zero,zero,OP_ZERO);
}
for(int i = 0;i<n;i++)v.push_back(lv[i]);
for(int i = 0;i<m;i++)v.push_back(rv[i]);
while(v.size() != B)v.push_back(Obj());
bitonic_merge(0,v.size()-1,v,1);
return ptr;
cerr<<"bitonic2"<<endl;
assert(v.size() == B);
vv.clear();
for(int i = B-n-m;i<B;i++)vv.push_back(v[i]);
SWEEP2(vv);
for(int i = 0;i<vv.size();i++)v.end()[-1-i] = vv.end()[-1-i];
cerr<<"sweep2"<<endl;
undo_bitonic(v);
cerr<<"undo"<<endl;
for(int i = 0;i<n;i++)lv[i] = v[i];
for(int i = 0;i<m;i++)rv[i] = v[i+n];
for(int i = n*OBJ_LEN;i<la;i++)q.push(i);
cerr<<"apply alice"<<endl;
apply_perm(n,0,lv);
assert(q.empty());
lv.resize(n);
for(int i = 0;i<n;i++){
for(int j = 0;j<NUM_LEN;j++){
outputs_circuit[i][j] = lv[i].val+j;
}
}
cerr<<"circuit out!"<<endl;
return ptr;
}
