Submission #1008591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008591		pcc	Alice, Bob, and Circuit (APIO23_abc)	C++17	0 / 100	1213 ms	2097152 KiB

abc

#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;

// 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());
	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;
	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';
	}
	//cerr<<"la = "<<ptr<<','<<n*OBJ_LEN<<','<<code.size()<<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.rbegin(),v.rend());
	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].sc>v[b].sc;});

	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].fs>>j)&1;
		}
		outputs_bob[ptr++] = 0;
		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';
	}
	//cerr<<"bob out!"<<endl;
	return ptr;
}


int zero,one;

struct Obj{
	vi name1,name2,val;//name1.size = name2.size = NAME_LEN,val.size = NUM_LEN
	int tp;//pointer to type
	Obj(){
		for(int i = 0;i<NAME_LEN;i++)name1.push_back(zero);
		for(int i = 0;i<NAME_LEN;i++)name2.push_back(zero);
		tp = zero;
		for(int i = 0;i<NUM_LEN;i++)val.push_back(zero);
	}
	Obj(int a){
		name1.clear();name2.clear();val.clear();
		for(int i = 0;i<NAME_LEN;i++)name1.push_back(a++);
		for(int i = 0;i<NAME_LEN;i++)name2.push_back(a++);
		tp = a++;
		for(int i = 0;i<NUM_LEN;i++)val.push_back(a++);
	}
	Obj(vi v){
		assert(v.size() == OBJ_LEN);
		name1.clear();name2.clear();val.clear();
		int a = 0;
		for(int i = 0;i<NAME_LEN;i++)name1.push_back(v[a++]);
		for(int i = 0;i<NAME_LEN;i++)name2.push_back(v[a++]);
		tp = v[a++];
		for(int i = 0;i<NUM_LEN;i++)val.push_back(v[a++]);
	}
	vi getval(){
		vi re;
		for(auto &i:name1)re.push_back(i);
		for(auto &i:name2)re.push_back(i);
		re.push_back(tp);
		for(auto &i:val)re.push_back(i);
		assert(re.size() == OBJ_LEN);
		return re;
	}
};

// 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<vi(vi,vi)> FULL_ADDER = [&](vi a,vi b){//adds a,b and returns c
		assert(a.size() == b.size()&&a.size() == NUM_LEN);
		//cerr<<"ADDER IN!"<<endl;
		vi re;
		int car = zero;
		for(int i = 0;i<NUM_LEN;i++){
			auto [t1,t2] = HALF_ADDER(a[i],b[i]);
			auto [t3,t4] = HALF_ADDER(t1,car);
			re.push_back(t3);
			car = addop(t2,t4,OP_OR);
		}
		//cerr<<"ADDER OUT!"<<endl;
		assert(re.size() == NUM_LEN);
		return re;
	};
	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(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){
		//cerr<<"SWAPIF IN!"<<endl;
		vi a = oa.getval(),b = ob.getval();
		assert(a.size() == OBJ_LEN&&b.size() == OBJ_LEN);
		pair<vi,vi> p;
		for(int i = 0;i<OBJ_LEN;i++){
			//cerr<<i<<":"<<a[i]<<','<<b[i]<<endl;
			int xorsum = addop(a[i],b[i],OP_XOR);
			int tmp = addop(f,b[i],OP_AND);
			p.fs.push_back(addop(xorsum,tmp,OP_XOR));
			p.sc.push_back(addop(xorsum,p.fs.back(),OP_XOR));
			//cerr<<i<<":"<<p.fs.back()<<','<<p.sc.back()<<endl;
		}
		oa = Obj(p.fs),ob = Obj(p.sc);
		//cerr<<"SWAPIF OUT!"<<endl;
		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;
		////cerr<<l<<' '<<r<<','<<v.size()<<endl;
		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(auto &i:v[i+len].name1)va.push_back(i);
				vb.push_back(v[i].tp);for(auto &i:v[i].name1)vb.push_back(i);
			}
			else{
				va.push_back(v[i+len].tp);for(auto &i:v[i+len].name2)va.push_back(i);
				vb.push_back(v[i].tp);for(auto &i:v[i].name2)vb.push_back(i);
			}
			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;
	};
	////cerr<<"circuit out!"<<endl;return ptr;

	queue<int> q;
	function<bool()> 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;
		//cerr<<"apply perm "<<l<<','<<n<<endl;
		for(int i = 0;i<m;i++){
			while(v.size()<=l+m+i)v.push_back(Obj());
			SWAPIF(v[l+i],v[l+m+i],getcode());
		}
		apply_perm(m,l,v);
		apply_perm(m,l+m,v);
		//cerr<<"apply perm2 "<<l<<','<<n<<endl;
		for(int i = 0;i<m;i++){
			SWAPIF(v[l+i],v[l+m+i],getcode());
		}
		return;
	};

	function<void(vector<Obj>&)> SWEEP1 = [&](vector<Obj> &v){
		//cerr<<"SWEEP1 IN!"<<endl;
		vi x = vi(NUM_LEN,zero);
		for(auto &i:v){
			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);
				int t3 = addop(i.tp,x[j],OP_LESS);
				int t4 = addop(i.tp,i.val[j],OP_AND);
				i.val[j] = addop(t1,t2,OP_OR);
				x[j] = addop(t3,t4,OP_OR);
			}
		}
		//cerr<<"SWEEP1 OUT!"<<endl;
		return;
	};

	function<void(vector<Obj>&)> SWEEP2 = [&](vector<Obj> &v){
		//cerr<<"SWEEP2 IN!"<<endl;
		vi x = vi(NUM_LEN,zero);
		int C = 0;
		for(auto &i:v){
			//cerr<<C<<endl;
			assert(i.getval().size() == OBJ_LEN);
			vi sum = FULL_ADDER(x,i.val);
			for(int j = 0;j<OBJ_LEN;j++){
				int t1 = addop(i.tp,x[j],OP_AND);
				int t2 = addop(i.tp,i.val[j],OP_LESS);
				i.val[j] = addop(t1,t2,OP_OR);
				int t3 = addop(i.tp,sum[j],OP_LESS);
				x[j] = t3;
			}
			//cerr<<C++<<endl;
		}
		//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 = addop(0,0,OP_ZERO);
	one = addop(0,0,OP_ONE);
	//cerr<<"zero,one added"<<endl;
	vector<Obj> lv(0,Obj()),rv(0,Obj());
	vector<Obj> v(0,Obj());
	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() != 2048)v.push_back(Obj());
	//cerr<<"variable initialized"<<endl;
	bitonic_merge(0,v.size()-1,v,0);
	//cerr<<"bitonic1"<<endl;
	SWEEP1(v);
	//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 = 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 = 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++)v.push_back(lv[i]);
	for(int i = 0;i<m;i++)v.push_back(rv[i]);
	while(v.size() != 2048)v.push_back(Obj());
	bitonic_merge(0,v.size()-1,v,1);
	//cerr<<"bitonic2"<<endl;
	assert(v.size() == 2048);
	////cerr<<"n = "<<n<<endl;cerr<<"m = "<<m<<endl;return 0;
	SWEEP2(v);
	//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);
	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;
}

Compilation message (stderr)

abc.cpp: In function 'void PERM::encode(std::vector<int>)':
abc.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int i = 1;i<cyc.size();i++){
      |                  ~^~~~~~~~~~~
abc.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int i = 1;i<tags.size();i+=2){
      |                  ~^~~~~~~~~~~~
abc.cpp: In lambda function:
abc.cpp:103:14: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |   if(s.size()>i)re += ts;
      |      ~~~~~~~~^~
abc.cpp: In function 'int bob(int, const char (*)[5], const char (*)[5], bool*)':
abc.cpp:189:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |  for(int i = 0;i<code.size();i++){
      |                ~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from abc.cpp:3:
abc.cpp: In lambda function:
abc.cpp:341:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  341 |    assert(0<=a&&a<v.size()&&0<=b&&b<v.size());
      |                 ~^~~~~~~~~
abc.cpp:341:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  341 |    assert(0<=a&&a<v.size()&&0<=b&&b<v.size());
      |                                   ~^~~~~~~~~
abc.cpp:337:7: warning: unused variable 'C' [-Wunused-variable]
  337 |   int C = 0;
      |       ^
abc.cpp: In lambda function:
abc.cpp:364:18: warning: comparison of integer expressions of different signedness: 'std::vector<Obj>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  364 |    while(v.size()<=l+m+i)v.push_back(Obj());
      |          ~~~~~~~~^~~~~~~
abc.cpp: In lambda function:
abc.cpp:396:7: warning: unused variable 'C' [-Wunused-variable]
  396 |   int C = 0;
      |       ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 6
• Subtask 7: 0 / 18
• Subtask 8: 0 / 10
• Subtask 9: 0 / 6