#include "vision.h"
#include <cassert>
using namespace std;
int log2(int n){
int res = 0, tres = 1;
while(tres < n){
tres <<= 1;
res++;
}
return res;
}
void construct_network(int H, int W, int K) {
if (H * W == 2) {
add_and({0, 1});
return;
}
int log2H = log2(H);
int log2W = log2(W);
int z = add_and({0,1,2});
int o = add_not(z);
vector<int> rows;
for (int x = 0; x < H; ++x) {
vector<int> tr;
for (int y = 0; y < W; ++y) {
tr.push_back(x * W + y);
}
rows.push_back(add_xor(tr));
}
vector<int> cols;
for (int y = 0; y < W; ++y) {
vector<int> tc;
for (int x = 0; x < H; ++x) {
tc.push_back(x * W + y);
}
cols.push_back(add_xor(tc));
}
vector<int> Hind;
for (int divs = 0; divs < log2H; divs++) {
vector<int> tN;
for (int x = 0; x < H; ++x) {
if ((x >> divs) & 1) tN.push_back(rows[x]);
}
int raw = add_xor(tN);
int nadj = o;
if (divs != 0 && (1 << divs) + 1 < H){
vector<int> boths;
for (int cen = 1 << divs; cen < H; cen += 1 << divs) {
vector<int> pre;
for (int x = cen - (1 << (divs - 1)); x < cen; ++x) {
pre.push_back(rows[x]);
}
int inpre = add_xor(pre);
vector<int> post;
for (int x = cen; x < cen + (1 << (divs - 1)) && x < H; ++x) {
post.push_back(rows[x]);
}
int inpost = add_xor(post);
boths.push_back(add_and({inpre, inpost}));
}
int adj = add_or(boths);
nadj = add_not(adj);
}
Hind.push_back(add_and({raw, nadj}));
}
for (int i = 0; i < log2W - log2H; ++i) {
Hind.push_back(add_and({z}));
}
vector<int> Wind;
for (int divs = 0; divs < log2W; divs++) {
vector<int> tN;
for (int y = 0; y < W; ++y) {
if ((y >> divs) & 1) tN.push_back(cols[y]);
}
int raw = add_xor(tN);
int nadj = o;
if (divs != 0 && (1 << divs) + 1 < W){
vector<int> boths;
for (int cen = 1 << divs; cen < W; cen += 1 << divs) {
vector<int> pre;
for (int y = cen - (1 << (divs - 1)); y < cen; ++y) {
pre.push_back(cols[y]);
}
int inpre = add_xor(pre);
vector<int> post;
for (int y = cen; y < cen + (1 << (divs - 1)) && y < H; ++y) {
post.push_back(cols[y]);
}
int inpost = add_xor(post);
boths.push_back(add_and({inpre, inpost}));
}
int adj = add_or(boths);
nadj = add_not(adj);
}
Wind.push_back(add_and({raw, nadj}));
}
for (int i = 0; i < log2H - log2W; ++i) {
Wind.push_back(add_and({z}));
}
assert(Hind.size() == Wind.size());
int addbits = max(log2H, log2W);
vector<int> addeds, carries;
addeds.push_back(add_xor({Wind[0], Hind[0]}));
carries.push_back(add_and({Wind[0], Hind[0]}));
for (int i = 1; i < addbits; ++i) {
addeds.push_back(add_xor({Wind[i], Hind[i], carries[i - 1]}));
int o1 = add_and({Wind[i], Hind[i]});
int o2 = add_and({carries[i - 1], Hind[i]});
int o3 = add_and({Wind[i], carries[i - 1]});
carries.push_back(add_or({o1, o2, o3}));
}
addeds.push_back(add_and({carries.back()}));
vector<int> Kbits;
for (int i = 0; i < addeds.size(); ++i) {
if (K & 1) Kbits.push_back(add_and({o}));
else Kbits.push_back(add_and({z}));
K >>=1;
}
assert(K == 0);
vector<int> XORS;
for (int i = 0; i < addeds.size(); ++i) {
XORS.push_back(add_xor({addeds[i], Kbits[i]}));
}
vector<int> NOTS;
for (int i = 0; i < XORS.size(); ++i) {
NOTS.push_back(add_not(XORS[i]));
}
add_and(NOTS);
}
Compilation message
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int i = 0; i < addeds.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
vision.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int i = 0; i < addeds.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
vision.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < XORS.size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 1), (0, 2), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 1), (0, 2), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 1), (0, 2), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 1), (0, 2), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
WA in grader: Instruction with no inputs |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
360 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
340 KB |
WA in grader: Instruction with no inputs |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1224 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
WA in grader: Instruction with no inputs |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 1), (0, 2), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
