#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
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
static int l, la, lb;
static int* operations;
static int (*operands)[2];
static int (*outputs)[16];
int makeGate(int op, int x0, int x1) {
operations[l] = op;
operands[l][0] = x0;
operands[l][1] = x1;
return l++;
}
struct Gate;
using GatePtr = shared_ptr<Gate>;
struct Gate {
int id;
Gate() : id(-1) { }
virtual ~Gate() { }
virtual int materialize() = 0;
};
struct InputGate : Gate {
int from, index;
InputGate(int from, int index) : from(from), index(index) { }
int materialize() override {
if (id != -1)
return id;
return id = from * la + index;
}
};
struct ComputeGate : Gate {
GatePtr inputs[2];
int op;
ComputeGate(const GatePtr& a, const GatePtr& b, int op) : op(op) {
inputs[0] = a;
inputs[1] = b;
}
int materialize() override {
if (id != -1)
return id;
return id = makeGate(op, inputs[0]->materialize(), inputs[1]->materialize());
}
};
struct NotGate : Gate {
GatePtr input;
NotGate(const GatePtr& input) : input(input) { }
int materialize() override {
if (id != -1)
return id;
return id = makeGate(OP_NOT_X0, input->materialize(), 0);
}
};
struct ConstGate : Gate {
bool value;
ConstGate(bool value) : value(value) { }
int materialize() override {
if (id != -1)
return id;
return id = makeGate(value * OP_ONE, 0, 0);
}
};
struct UndefinedGate : Gate {
int materialize() override {
if (id != -1)
return id;
return id = makeGate(OP_ZERO, 0, 0);
}
};
static int dual(int op) {
return op & 9 | (op & 2) << 1 | (op & 4) >> 1;
}
static GatePtr undefinedGate() {
static GatePtr undefined = make_shared<UndefinedGate>();
return undefined;
}
static GatePtr constGate(bool value) {
static GatePtr consts[2] = { make_shared<ConstGate>(false), make_shared<ConstGate>(true) };
return consts[value];
}
static GatePtr notGate(const GatePtr& input) {
if (auto c = dynamic_cast<ConstGate*>(input.get()))
return constGate(!c->value);
if (auto u = dynamic_cast<UndefinedGate*>(input.get()))
return undefinedGate();
if (auto n = dynamic_cast<NotGate*>(input.get()))
return n->input;
return make_shared<NotGate>(input);
}
static map<tuple<GatePtr, GatePtr, int>, GatePtr> computeGateCache;
static GatePtr computeGate(const GatePtr& a, const GatePtr& b, int op) {
if (op == OP_ZERO || op == OP_ONE)
return constGate(op == OP_ONE);
if (op == OP_X0)
return a;
if (op == OP_X1)
return b;
if (op == OP_NOT_X0)
return notGate(a);
if (op == OP_NOT_X1)
return notGate(b);
if (NotGate* na = dynamic_cast<NotGate*>(a.get()))
return computeGate(b, a, dual(op));
if (NotGate* nb = dynamic_cast<NotGate*>(b.get()))
return computeGate(a, nb->input, op >> 2 | (op & 3) << 2);
UndefinedGate* ua = dynamic_cast<UndefinedGate*>(a.get()), *ub = dynamic_cast<UndefinedGate*>(b.get());
if (ua && ub)
return undefinedGate();
if (ua || ub) {
if (op == OP_XOR || op == OP_EQUAL)
return undefinedGate();
return constGate(__builtin_popcount(op) >> 1);
}
ConstGate* ca = dynamic_cast<ConstGate*>(a.get()), *cb = dynamic_cast<ConstGate*>(b.get());
if (ca && cb)
return constGate(op >> (ca->value | cb->value << 1) & 1);
if (ca)
return computeGate(b, a, dual(op));
if (cb) {
int x = op >> (cb->value << 1) & 3;
if (x == 1)
return notGate(a);
if (x == 2)
return a;
return constGate(x == 3);
}
auto& result = computeGateCache[make_tuple(a, b, op)];
if (result)
return result;
result = make_shared<ComputeGate>(a, b, op);
return result;
}
static GatePtr inputGate(int from, int index) {
return make_shared<InputGate>(from, index);
}
struct Bit {
GatePtr gate;
Bit() : gate(undefinedGate()) { }
explicit Bit(bool value) : gate(constGate(value)) { }
Bit(const GatePtr& gate) : gate(gate) { }
};
static Bit operator&(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_AND);
}
static Bit operator|(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_OR);
}
static Bit operator^(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_XOR);
}
static Bit operator~(const Bit& a) {
return notGate(a.gate);
}
static Bit operator==(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_EQUAL);
}
static Bit operator!=(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_XOR);
}
static Bit operator>=(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_GEQ);
}
static Bit operator<=(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_LEQ);
}
static Bit operator>(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_GREATER);
}
static Bit operator<(const Bit& a, const Bit& b) {
return computeGate(a.gate, b.gate, OP_LESS);
}
struct Integer : vector<Bit> {
using vector<Bit>::vector;
};
static Integer operator&(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Integer result;
for (int i = 0; i < a.size(); i++)
result.push_back(a[i] & b[i]);
return result;
}
static Integer operator|(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Integer result;
for (int i = 0; i < a.size(); i++)
result.push_back(a[i] | b[i]);
return result;
}
static Integer operator^(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Integer result;
for (int i = 0; i < a.size(); i++)
result.push_back(a[i] ^ b[i]);
return result;
}
static Integer operator~(const Integer& a) {
Integer result;
for (int i = 0; i < a.size(); i++)
result.push_back(~a[i]);
return result;
}
static Integer operator+(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Integer result;
Bit carry(false);
for (int i = 0; i < a.size(); i++) {
Bit x = a[i] ^ b[i];
result.push_back(x ^ carry);
carry = (a[i] & b[i]) | (x & carry);
}
return result;
}
static Integer& operator+=(Integer& a, const Integer& b) {
return a = a + b;
}
static Bit operator==(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Bit result(true);
for (int i = 0; i < a.size(); i++)
result = result & (a[i] == b[i]);
return result;
}
static Bit operator!=(const Integer& a, const Integer& b) {
return ~(a == b);
}
static Bit operator<(const Integer& a, const Integer& b) {
assert(a.size() == b.size());
Bit result(false);
for (int i = a.size() - 1; i >= 0; i--)
result = (a[i] < b[i]) | ((a[i] == b[i]) & result);
return result;
}
static Bit operator>(const Integer& a, const Integer& b) {
return b < a;
}
static Bit operator<=(const Integer& a, const Integer& b) {
return ~(a > b);
}
static Bit operator>=(const Integer& a, const Integer& b) {
return ~(a < b);
}
static Integer inputInteger(int from, int index, int size) {
Integer result;
for (int i = 0; i < size; i++)
result.push_back(inputGate(from, index + i));
return result;
}
static Integer zeroInteger(int size) {
Integer result;
for (int i = 0; i < size; i++)
result.push_back(Bit(false));
return result;
}
static int materialize(const Bit& bit) {
return bit.gate->materialize();
}
static vector<int> materialize(const Integer& integer) {
vector<int> result;
for (int i = 0; i < integer.size(); i++)
result.push_back(materialize(integer[i]));
return result;
}
// Alice
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs[]
) {
for (int i = 0; i < 16; i++)
outputs[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[]
) {
return m;
}
// Circuit
int // returns l
circuit(
/* in */ const int la,
/* in */ const int lb,
/* out */ int operations[],
/* out */ int operands[][2],
/* out */ int outputs[][16]
) {
::l = la + lb;
::la = la;
::lb = lb;
::operations = operations;
::operands = operands;
::outputs = outputs;
Integer a = inputInteger(0, 0, 16);
Integer sum = zeroInteger(16);
for (int i = 0; i < lb; i++)
sum += a;
vector<int> result = materialize(sum);
memcpy(outputs[0], result.data(), 16 * sizeof(int));
return ::l;
}
Compilation message
abc.cpp: In function 'int dual(int)':
abc.cpp:97:15: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
97 | return op & 9 | (op & 2) << 1 | (op & 4) >> 1;
| ~~~^~~
abc.cpp: In function 'GatePtr notGate(const GatePtr&)':
abc.cpp:113:14: warning: unused variable 'u' [-Wunused-variable]
113 | if (auto u = dynamic_cast<UndefinedGate*>(input.get()))
| ^
abc.cpp: In function 'GatePtr computeGate(const GatePtr&, const GatePtr&, int)':
abc.cpp:133:18: warning: unused variable 'na' [-Wunused-variable]
133 | if (NotGate* na = dynamic_cast<NotGate*>(a.get()))
| ^~
abc.cpp: In function 'Integer operator&(const Integer&, const Integer&)':
abc.cpp:215:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator|(const Integer&, const Integer&)':
abc.cpp:222:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator^(const Integer&, const Integer&)':
abc.cpp:229:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator~(const Integer&)':
abc.cpp:235:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator+(const Integer&, const Integer&)':
abc.cpp:243:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
243 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
abc.cpp: In function 'Bit operator==(const Integer&, const Integer&)':
abc.cpp:256:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
256 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
abc.cpp: In function 'std::vector<int> materialize(const Integer&)':
abc.cpp:296:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
296 | for (int i = 0; i < integer.size(); i++)
| ~~^~~~~~~~~~~~~~~~
abc.cpp: At global scope:
abc.cpp:276:12: warning: 'Bit operator>=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
276 | static Bit operator>=(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:273:12: warning: 'Bit operator<=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
273 | static Bit operator<=(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:260:12: warning: 'Bit operator!=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
260 | static Bit operator!=(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:233:16: warning: 'Integer operator~(const Integer&)' defined but not used [-Wunused-function]
233 | static Integer operator~(const Integer& a) {
| ^~~~~~~~
abc.cpp:226:16: warning: 'Integer operator^(const Integer&, const Integer&)' defined but not used [-Wunused-function]
226 | static Integer operator^(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:219:16: warning: 'Integer operator|(const Integer&, const Integer&)' defined but not used [-Wunused-function]
219 | static Integer operator|(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:212:16: warning: 'Integer operator&(const Integer&, const Integer&)' defined but not used [-Wunused-function]
212 | static Integer operator&(const Integer& a, const Integer& b) {
| ^~~~~~~~
abc.cpp:202:12: warning: 'Bit operator>(const Bit&, const Bit&)' defined but not used [-Wunused-function]
202 | static Bit operator>(const Bit& a, const Bit& b) {
| ^~~~~~~~
abc.cpp:199:12: warning: 'Bit operator<=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
199 | static Bit operator<=(const Bit& a, const Bit& b) {
| ^~~~~~~~
abc.cpp:196:12: warning: 'Bit operator>=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
196 | static Bit operator>=(const Bit& a, const Bit& b) {
| ^~~~~~~~
abc.cpp:193:12: warning: 'Bit operator!=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
193 | static Bit operator!=(const Bit& a, const Bit& b) {
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1188 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1188 KB |
Correct! |
| 2 |
Correct |
3 ms |
1208 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1188 KB |
Correct! |
| 2 |
Correct |
3 ms |
1208 KB |
Correct! |
| 3 |
Correct |
85 ms |
19908 KB |
Correct! |
| 4 |
Correct |
89 ms |
19940 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1672 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1672 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1672 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
24904 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
24904 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1188 KB |
Correct! |
| 2 |
Correct |
3 ms |
1208 KB |
Correct! |
| 3 |
Correct |
85 ms |
19908 KB |
Correct! |
| 4 |
Correct |
89 ms |
19940 KB |
Correct! |
| 5 |
Incorrect |
8 ms |
1672 KB |
WA Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect. |
| 6 |
Halted |
0 ms |
0 KB |
- |
