#include "vision.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
vi rows;
int rangeOrRow(int l, int r) {
vi Ns;
for (int i = l; i < r; i++) {
Ns.push_back(rows[i]);
}
return add_or(Ns);
}
vi cols;
void construct_network(int H, int W, int K) {
rows = vi(H);
loop(i, H) {
vi Ns;
loop(j, W) {
Ns.push_back(i * W + j);
}
rows[i] = add_or(Ns);
//add_log(rows[i]);
}
cols = vi(W);
loop(j, W) {
vi Ns;
loop(i, H) {
Ns.push_back(i * W + j);
}
cols[j] = add_or(Ns);
//add_log(cols[j]);
}
//int zero = add_or(rows);
//cout << "Rowbits: " << endl;
vi rowBits;
loop(bit, 8) {
vi ands;
loop(i, H - (1 << bit)) {
vi rs;
for (int j = i + (1 << bit); j < H; j += 2 * (1 << bit)) {
for (int j2 = j; j2 < min(H, j + (1 << bit)); j2++) {
rs.push_back(rows[j2]);
}
}
if (rs.size() == 0) {
break;
}
int l = rows[i];
int r = add_or(rs);
ands.push_back(add_and({l, r}));
}
if (ands.size() == 0) {
break;
}
rowBits.push_back(add_or(ands));
//add_log(rowBits.back());
}
//cout << "Colbits: " << endl;
vi colBits;
loop(bit, 8) {
vi ands;
loop(i, W - (1 << bit)) {
vi rs;
for (int j = i + (1 << bit); j < W; j += 2 * (1 << bit)) {
for (int j2 = j; j2 < min(W, j + (1 << bit)); j2++) {
rs.push_back(cols[j2]);
}
}
if (rs.size() == 0) {
break;
}
int l = cols[i];
int r = add_or(rs);
ands.push_back(add_and({l, r}));
}
if (ands.size() == 0) {
break;
}
colBits.push_back(add_or(ands));
//add_log(colBits.back());
}
const int zero = add_not(add_or(rows));
if (colBits.size() > rowBits.size()) {
swap(colBits, rowBits);
}
vi sum;
int carry = zero;
loop(bit, colBits.size()) {
sum.push_back(add_xor({colBits[bit], rowBits[bit], carry}));
carry = add_or({
add_and({colBits[bit], rowBits[bit]}),
add_and({colBits[bit], carry}),
add_and({carry, rowBits[bit]})
});
}
for (int bit = colBits.size(); bit < rowBits.size(); bit++) {
sum.push_back(add_xor({colBits[bit], carry}));
carry = add_and({colBits[bit], carry});
}
sum.push_back(carry);
loop(bit, sum.size()) {
if ((K & (1 << bit)) == 0) {
sum[bit] = add_not(sum[bit]);
}
}
if (K >= (1 << sum.size())) {
add_not(add_not(zero));
return;
}
add_and(sum);
}
Compilation message
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define loop(X, N) for(int X = 0; X < (N); X++)
| ^
vision.cpp:136:5: note: in expansion of macro 'loop'
136 | loop(bit, colBits.size()) {
| ^~~~
vision.cpp:144:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int bit = colBits.size(); bit < rowBits.size(); bit++) {
| ~~~~^~~~~~~~~~~~~~~~
vision.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define loop(X, N) for(int X = 0; X < (N); X++)
| ^
vision.cpp:150:5: note: in expansion of macro 'loop'
150 | loop(bit, sum.size()) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
604 KB |
on inputs (0, 0), (3, 28), expected 1, but computed 0 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2776 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
860 KB |
on inputs (43, 55), (43, 56), expected 1, but computed 0 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
