oj.uz

Submission #749954

# Submission time Handle Problem Language Result Execution time Memory
749954 2023-05-29T02:17:19 Z jamezzz Alice, Bob, and Circuit (APIO23_abc) C++17
66 / 100
 490 ms 488428 KB 
#include "abc.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define INF 1023456789
#define LINF 1023456789123456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define disc(x) x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef vector<ii> vii;
typedef pair<double,int> di;
typedef tuple<double,int,int> dii;

// 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


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
	string s[n];
	vector<string> v;
	for(int i=0;i<n;++i){
		s[i]="";
		for(int j=0;j<4;++j){
			if(names[i][j]==0)break;
			s[i]+=names[i][j];
		}
		v.pb(s[i]);
	}
	sort(all(v));
	for(int i=0;i<n;++i){
		int pos=lower_bound(all(v),s[i])-v.begin();
		for(int j=0;j<16;++j){
			//j-th bit is is pos*16 + j
			outputs_alice[pos*16+j]=(numbers[i]>>j)&1;
		}
		for(int j=0;j<10;++j){
			outputs_alice[n*16+i*10+j]=(pos>>j)&1;
		}
	}
    return n*26;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
	string ss[m],rs[m];
	vector<string> v;
	for(int i=0;i<m;++i){
		ss[i]="";
		for(int j=0;j<4;++j){
			if(senders[i][j]==0)break;
			ss[i]+=senders[i][j];
		}
		v.pb(ss[i]);
		rs[i]="";
		for(int j=0;j<4;++j){
			if(recipients[i][j]==0)break;
			rs[i]+=recipients[i][j];
		}
		v.pb(rs[i]);
	}
	sort(all(v));
	disc(v);
	for(int i=0;i<m;++i){
		int poss=lower_bound(all(v),ss[i])-v.begin();
		for(int j=0;j<10;++j){
			//j-th bit is 20*i + j
			outputs_bob[20*i+j]=(poss>>j)&1;
		}
		int posr=lower_bound(all(v),rs[i])-v.begin();
		for(int j=0;j<10;++j){
			//j-th bit is 20*i + j + 10
			outputs_bob[20*i+j+10]=(posr>>j)&1;
		}
	}
    return 20*m;
}

int n,m,cnt,num[705][15];

vector<int> get_send(int i,int s){
	vector<int> res;
	for(int j=0;j<10;++j){
		res.pb({s+i*20+j});
	}
	return res;
}

vector<int> get_rece(int i,int s){
	vector<int> res;
	for(int j=0;j<10;++j){
		res.pb({s+i*20+j+10});
	}
	return res;
}

// 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]
) {
	for(int i=0;i<la+lb;++i){
		operations[i]=-1;
		operands[i][0]=operands[i][1]=0;
	}
	cnt=la+lb;
	n=la/26,m=lb/20;
	
	operations[cnt]=OP_ZERO;
	operands[cnt][0]=operands[cnt][1]=0;
	int ZERO=cnt++;
	
	operations[cnt]=OP_ONE;
	operands[cnt][0]=operands[cnt][1]=0;
	int ONE=cnt++;
	
	//fill in the numbers
	for(int i=0;i<n;++i){
		for(int j=0;j<10;++j){
			if(i&(1<<j))num[i][j]=ONE;
			else num[i][j]=ZERO;
		}
	}
	
	vector<int> output;
	for(int i=0;i<n;++i){
		for(int j=0;j<16;++j){
			output.pb(ZERO);
		}
	}
	
	//printf("start process\n");
	
	for(int i=0;i<m;++i){
		//printf("adding %d\n",i);
		vector<int> send=get_send(i,la);
		vector<int> rece=get_rece(i,la);
		
		//printf("calc toadd\n");
		
		vector<int> val(16,ZERO);
		//pv==1 if sending
		for(int i=0;i<n;++i){
			int pv=ONE;
			
			for(int j=0;j<10;++j){
				//check if bits are same
				
				operations[cnt]=OP_EQUAL;
				operands[cnt][0]=num[i][j];
				operands[cnt][1]=send[j];
				int cur=cnt++;
				
				operations[cnt]=OP_AND;
				operands[cnt][0]=pv;
				operands[cnt][1]=cur;
				pv=cnt++;
			}
			
			for(int j=0;j<16;++j){
				operations[cnt]=OP_AND;
				operands[cnt][0]=pv;
				operands[cnt][1]=i*16+j;
				int tmp=cnt++;
				
				operations[cnt]=OP_OR;
				operands[cnt][0]=tmp;
				operands[cnt][1]=val[j];
				val[j]=cnt++;
			}
		}
		
		vector<int> toadd;
		//00..00 11..11 00..00 ...
		for(int i=0;i<n;++i){
			int pv=ONE;
			
			for(int j=0;j<10;++j){
				//check if bits are same
				
				operations[cnt]=OP_EQUAL;
				operands[cnt][0]=n*16+i*10+j;
				operands[cnt][1]=rece[j];
				int cur=cnt++;
				
				operations[cnt]=OP_AND;
				operands[cnt][0]=pv;
				operands[cnt][1]=cur;
				pv=cnt++;
			}
			
			for(int j=0;j<16;++j){
				operations[cnt]=OP_AND;
				operands[cnt][0]=pv;
				operands[cnt][1]=val[j];
				toadd.pb(cnt);
				cnt++;
			}
		}
		
		//printf("calc newoutput\n");
		
		vector<int> newoutput;
		for(int i=0;i<n;++i){
			int c=ZERO;
			for(int j=0;j<16;++j){
				int a=output[i*16+j],b=toadd[i*16+j];
				
				//calculate low bit
				operations[cnt]=OP_XOR;
				operands[cnt][0]=a;
				operands[cnt][1]=b;
				int tmp=cnt++;
				
				operations[cnt]=OP_XOR;
				operands[cnt][0]=tmp;
				operands[cnt][1]=c;
				int res=cnt++;
				
				newoutput.pb(res);
				
				//calculate carry
				operations[cnt]=OP_AND;
				operands[cnt][0]=b;
				operands[cnt][1]=c;
				int tmp1=cnt++;//B.C
				
				operations[cnt]=OP_OR;
				operands[cnt][0]=b;
				operands[cnt][1]=c;
				int tmp2=cnt++;//B+C
				
				operations[cnt]=OP_AND;
				operands[cnt][0]=a;
				operands[cnt][1]=tmp2;
				int tmp3=cnt++;//A.(B+C)
				
				operations[cnt]=OP_OR;
				operands[cnt][0]=tmp1;
				operands[cnt][1]=tmp3;
				c=cnt++;//(A.(B+C))+(B.C)
			}
		}
		swap(output,newoutput);
	}
	//printf("finish output\n");
	for(int i=0;i<n;++i){
		for(int j=0;j<16;++j){
			outputs_circuit[i][j]=output[i*16+j];
		}
	}
	//printf("return %d\n",cnt);
    return cnt;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1180 KB Correct!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1180 KB Correct!
2 Correct 3 ms 1196 KB Correct!

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1180 KB Correct!
2 Correct 3 ms 1196 KB Correct!
3 Correct 131 ms 14876 KB Correct!
4 Correct 113 ms 14892 KB Correct!

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2888 KB Correct!
2 Correct 104 ms 55460 KB Correct!
3 Correct 139 ms 71936 KB Correct!

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2888 KB Correct!
2 Correct 104 ms 55460 KB Correct!
3 Correct 139 ms 71936 KB Correct!
4 Correct 123 ms 55584 KB Correct!
5 Correct 159 ms 71680 KB Correct!

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2888 KB Correct!
2 Correct 104 ms 55460 KB Correct!
3 Correct 139 ms 71936 KB Correct!
4 Correct 123 ms 55584 KB Correct!
5 Correct 159 ms 71680 KB Correct!
6 Correct 105 ms 52144 KB Correct!
7 Correct 205 ms 108080 KB Correct!

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 490 ms 488428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 490 ms 488428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1180 KB Correct!
2 Correct 3 ms 1196 KB Correct!
3 Correct 131 ms 14876 KB Correct!
4 Correct 113 ms 14892 KB Correct!
5 Correct 10 ms 2888 KB Correct!
6 Correct 104 ms 55460 KB Correct!
7 Correct 139 ms 71936 KB Correct!
8 Correct 123 ms 55584 KB Correct!
9 Correct 159 ms 71680 KB Correct!
10 Correct 105 ms 52144 KB Correct!
11 Correct 205 ms 108080 KB Correct!
12 Runtime error 490 ms 488428 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -