이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
struct Number {
std::array<LogicGate, BIT_LENGTH> digits;
Number() {}
Number(std::vector<LogicGate> _digits){
for (int i = 0; i < BIT_LENGTH; 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 < BIT_LENGTH; 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 < BIT_LENGTH; i++){
LogicGate D(OP_XOR, A.digits[i], B.digits[i]);
if (i == BIT_LENGTH - 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 < BIT_LENGTH; 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>(BIT_LENGTH, zerobit));
Number current = A;
for (int i = 0; i < BIT_LENGTH; 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> 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 names[][5],
const u16 numbers[],
bool outputs_alice[]
) {
// For subtask A, we only need to send the number, since n = 1
for (int i = 0; i < BIT_LENGTH; i++)
outputs_alice[i] = ((numbers[0] >> i) & 1);
return BIT_LENGTH;
}
// Bob
int bob(
const int m,
const char senders[][5],
const char recipients[][5],
bool outputs_bob[]
) {
// For subtask A, we only need to send m, since n = 1
for (int i = 0; i < BIT_LENGTH; i++)
outputs_bob[i] = ((m >> i) & 1);
return BIT_LENGTH;
}
// Circuit
int circuit(
const int la,
const int lb,
int operations[],
int operands[][2],
int outputs_circuit[][16]
) {
initialize(la, lb);
std::vector<LogicGate> digits_A(la), digits_B(lb);
for (int i = 0; i < la; i++){
digits_A[i] = input_gates[i];
}
for (int i = 0; i < lb; i++){
digits_B[i] = input_gates[i + la];
}
Number numA(digits_A), numB(digits_B);
Number res = numA * numB;
// Output
return print_output(la, lb, operations, operands, outputs_circuit, {res});
}
# | 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... |