Submission #749510

#TimeUsernameProblemLanguageResultExecution timeMemory
749510SanguineChameleonAlice, Bob, and Circuit (APIO23_abc)C++17
12 / 100
160 ms12488 KiB
#include <bits/stdc++.h> #include "abc.h" 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 // Alice int // returns la alice( /* in */ const int n, /* in */ const char names[][5], /* in */ const unsigned short numbers[], /* out */ bool outputs_alice[] ) { for (int i = 0; i < 16; i++) { outputs_alice[i] = (numbers[0] >> i) & 1; } return 16; } // Bob int // returns lb bob( /* in */ const int m, /* in */ const char senders[][5], /* in */ const char recipients[][5], /* out */ bool outputs_bob[] ) { for (int i = 0; i < m; i++) { outputs_bob[i] = 1; } for (int i = m; i < 1024; i++) { outputs_bob[i] = 0; } return 1024; } int *operations; int (*operands)[2]; int cnt; int ZERO_GATE; int ONE_GATE; int gate(int op, int x, int y) { operations[cnt] = op; operands[cnt][0] = x; operands[cnt][1] = y; return cnt++; } pair<int, int> add(int x, int y, int z) { int sum1 = gate(OP_XOR, x, y); int rem1 = gate(OP_AND, x, y); int sum2 = gate(OP_XOR, sum1, z); int rem2 = gate(OP_AND, sum1, z); return make_pair(sum2, gate(OP_OR, rem1, rem2)); } vector<int> add(vector<int> num1, vector<int> num2) { vector<int> res(16); int rem = ZERO_GATE; for (int i = 0; i < 16; i++) { auto p = add(num1[i], num2[i], rem); res[i] = p.first; rem = p.second; } return res; } vector<int> mul(vector<int> num, int x) { vector<int> res(16); for (int i = 0; i < 16; i++) { res[i] = gate(OP_AND, num[i], x); } 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] ) { operations = _operations; operands = _operands; cnt = la + lb; ZERO_GATE = gate(OP_ZERO, 0, 0); ONE_GATE = gate(OP_ONE, 0, 0); vector<int> num(16); for (int i = 0; i < 16; i++) { num[i] = i; } vector<int> res(16, ZERO_GATE); for (int i = 0; i < 1024; i++) { res = add(res, mul(num, 16 + i)); } for (int i = 0; i < 16; i++) { outputs_circuit[0][i] = res[i]; } return cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...