#include <bits/stdc++.h>
#include "abc.h"
// 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
// Aliases
const int BIT_LENGTH = 16;
using u16 = unsigned short;
namespace {
struct GateOutput {
int operation;
int op0, op1;
GateOutput(int _op, int _op0, int _op1):
operation(_op), op0(_op0), op1(_op1) {
}
};
int gate_index;
std::vector<GateOutput> outputs;
}
struct LogicGate {
int idx;
int operation;
LogicGate() {}
LogicGate(int _idx) : idx(_idx) {
}
LogicGate(int _op, const LogicGate _op0, const LogicGate _op1) :
idx(gate_index++), operation(_op) {
outputs.emplace_back(operation, _op0.idx, _op1.idx);
}
};
namespace {
std::vector<LogicGate> input_gates;
LogicGate zerobit, onebit;
}
template <int LEN>
struct Number {
std::array<LogicGate, LEN> digits;
Number() {}
Number(std::vector<LogicGate> _digits){
for (int i = 0; i < LEN; i++) digits[i] = _digits[i];
}
// Cost: 74 operations
Number operator + (const Number &B) {
const Number A = *this;
Number result;
int shifted = 0;
for (int i = 0; i < LEN; i++){
if (B.digits[i].idx == zerobit.idx){
result.digits[i] = A.digits[i];
shifted++;
}
else break;
}
LogicGate carry = zerobit;
for (int i = shifted; i < LEN; i++){
LogicGate D(OP_XOR, A.digits[i], B.digits[i]);
if (i == LEN - 1){
LogicGate new_digit(OP_XOR, D, carry);
result.digits[i] = new_digit;
continue;
}
LogicGate CR(OP_AND, A.digits[i], B.digits[i]);
if (i == shifted){
result.digits[i] = D;
carry = CR;
continue;
}
LogicGate new_digit(OP_XOR, D, carry);
LogicGate carry2(OP_AND, carry, D);
LogicGate new_carry(OP_OR, CR, carry2);
result.digits[i] = new_digit;
carry = new_carry;
}
return result;
}
// Cost: 16 operations
Number operator & (const LogicGate gate){
const Number A = *this;
Number result;
for (int i = 0; i < LEN; i++){
if (A.digits[i].idx == zerobit.idx){
result.digits[i] = A.digits[i];
continue;
}
LogicGate new_digit(OP_AND, A.digits[i], gate);
result.digits[i] = new_digit;
}
return result;
}
// Cost: 0 operation
Number operator << (int shift) {
const Number A = *this;
Number result;
for (int i = 0; i < 16; i++){
int j = i - shift;
if (j < 0) result.digits[i] = zerobit;
else result.digits[i] = A.digits[j];
}
return result;
}
// Cost: 723 operations
Number operator * (const Number &B) {
const Number A = *this;
Number result(std::vector<LogicGate>(LEN, zerobit));
Number current = A;
for (int i = 0; i < LEN; i++){
result = result + (current & B.digits[i]);
current = current << 1;
}
return result;
}
};
// Cost: 2 operations
void initialize(const int la, const int lb){
gate_index = la + lb;
for (int i = 0; i < la + lb; i++){
LogicGate inp(i);
input_gates.push_back(inp);
}
zerobit = LogicGate(OP_ZERO, input_gates[0], input_gates[1]);
onebit = LogicGate(OP_ONE, input_gates[0], input_gates[1]);
}
int print_output(
const int la,
const int lb,
int operations[],
int operands[][2],
int outputs_circuit[][16],
std::vector<Number<BIT_LENGTH>> res
){
int crr = la + lb;
for (auto gate_output: outputs){
operations[crr] = gate_output.operation;
operands[crr][0] = gate_output.op0;
operands[crr][1] = gate_output.op1;
crr++;
}
for (int i = 0; i < (int)res.size(); i++){
for (int j = 0; j < BIT_LENGTH; j++){
outputs_circuit[i][j] = res[i].digits[j].idx;
}
}
return crr;
}
// Alice
int alice(
const int n,
const char raw_names[][5],
const u16 numbers[],
bool outputs_alice[]
) {
std::vector<std::string> names(n);
for (int i = 0; i < n; i++){
names[i] = std::string(raw_names[i]);
}
std::vector<std::pair<std::string, int>> vec(n);
for (int i = 0; i < n; i++){
vec[i] = {names[i], i};
}
std::sort(vec.begin(), vec.end());
std::vector<int> position(n);
for (int i = 0; i < n; i++){
position[vec[i].second] = i;
}
int crr = 0;
// Send numbers
for (int i = 0; i < n; i++){
u16 num = numbers[i];
for (int j = 0; j < BIT_LENGTH; j++){
outputs_alice[crr++] = (num >> j) & 1;
}
}
// Send permutation
for (int i = 0; i < n; i++){
for (int j = 0; j < 5; j++){ // 2^5 = 32 > 30 >= n
outputs_alice[crr++] = (position[i] >> j) & 1;
}
}
return crr;
}
// Bob
int bob(
const int m,
const char senders[][5],
const char recipients[][5],
bool outputs_bob[]
) {
std::vector<std::string> names;
for (int i = 0; i < m; i++){
names.push_back(std::string(senders[i]));
names.push_back(std::string(recipients[i]));
}
std::sort(names.begin(), names.end());
names.resize(std::unique(names.begin(), names.end()) - names.begin());
int n = names.size();
std::map<std::string, int> mp;
for (int i = 0; i < n; i++){
mp[names[i]] = i;
}
std::vector<std::vector<int>> matrix(m, std::vector<int>(m));
for (int i = 0; i < m; i++){
std::string str1 = std::string(senders[i]);
std::string str2 = std::string(recipients[i]);
int p1 = mp[str1], p2 = mp[str2];
matrix[p1][p2]++;
}
int crr = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int c = 0; c < 1; c++){
outputs_bob[crr++] = (matrix[i][j] >> c) & 1;
}
}
}
return crr;
}
// Circuit
int circuit(
const int la,
const int lb,
int operations[],
int operands[][2],
int outputs_circuit[][16]
) {
initialize(la, lb);
int n = sqrt(lb);
std::vector<Number<BIT_LENGTH>> ans(n);
for (int i = 0; i < n; i++){
ans[i] = Number<BIT_LENGTH>(std::vector(BIT_LENGTH, zerobit));
}
std::vector<Number<BIT_LENGTH>> nums(n);
for (int i = 0; i < n; i++){
std::vector<LogicGate> bits(BIT_LENGTH);
for (int j = 0; j < BIT_LENGTH; j++){
bits[j] = input_gates[i * BIT_LENGTH + j];
}
nums[i] = Number<BIT_LENGTH>(bits);
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
LogicGate cnt = input_gates[i * n + j + la];
ans[j] = ans[j] + (nums[i] & cnt);
}
}
return print_output(la, lb, operations, operands, outputs_circuit, ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1216 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1216 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1216 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
44 ms |
12808 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
44 ms |
12808 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1216 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
