이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |