#include "vision.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cassert>
#include <memory>
#include <numeric>
#include <functional>
#include <random>
#define ll long long
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define length(a) ((int)a.size())
using namespace std;
template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
while (begin != end) {
out << (*begin) << " ";
begin++;
}
out << endl;
}
template<class T> void output(const T &x, ostream &out = cerr) {
output(all(x), out);
}
template<class T> int chkmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class T> int chkmax(T &a, const T &b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
int ONE, ZERO;
vector<int> to_number(const vector<int> &A, int B) {
vector<int> res;
for (int b = 0; b < B; ++b) {
vector<int> cur;
for (int i = 0; i < A.size(); ++i) {
if ((i >> b) & 1) {
cur.push_back(A[i]);
}
}
if (cur.empty()) {
res.push_back(ZERO);
} else {
res.push_back(add_or(cur));
}
}
return res;
}
void flip(vector<int> &a) {
for (int i = 0; i < a.size(); ++i) {
a[i] = add_not(a[i]);
}
}
vector<int> sum(const vector<int> &a, const vector<int> &b) {
int B = a.size();
vector<int> res(B);
int p = -1;
for (int i = 0; i < B; ++i) {
if (p == -1) {
res[i] = add_xor({a[i], b[i]});
p = add_and({a[i], b[i]});
} else {
res[i] = add_xor({a[i], b[i], p});
p = add_or({add_and({a[i], b[i]}), add_and({a[i], p}), add_and({b[i], p})});
}
}
return res;
}
vector<int> from_bits(const vector<int> &a, int n, int B) {
vector<int> res(n);
for (int i = 0; i < n; ++i) {
vector<int> cur;
for (int j = 0; j < B; ++j) {
if ((i >> j) & 1) {
cur.push_back(a[j]);
} else {
cur.push_back(add_not(a[j]));
}
}
res[i] = add_and(cur);
}
return res;
}
vector<int> diff(const vector<int> &R, const vector<int> &L) {
int n = R.size();
int B = 1;
while ((1 << B) < n) {
B++;
}
cerr << "kek" << endl;
vector<int> num1 = to_number(R, B);
vector<int> num2 = to_number(L, B);
// cerr << "num1" << endl;
// output(all(num1));
// cerr << "num2" << endl;
// output(all(num2));
flip(num2);
vector<int> res = sum(num1, num2);
// cerr << "_res" << endl;
// output(all(res));
flip(res);
// cerr << "res" << endl;
// output(all(res));
vector<int> res_diff = from_bits(res, n, B);
return res_diff;
}
vector<int> diff(const vector<int> &a) {
cerr << "diff" << endl;
output(all(a));
int n = a.size();
vector<int> pref(n), suf(n);
pref[0] = add_not(a[0]);
for (int i = 1; i < n; ++i) {
pref[i] = add_and({add_not(a[i]), pref[i - 1]});
}
suf[n - 1] = add_not(a[n - 1]);
for (int i = n - 2; i >= 0; --i) {
suf[i] = add_and({add_not(a[i]), suf[i + 1]});
}
vector<int> L(n), R(n);
L[0] = a[0];
for (int i = 1; i < n; ++i) {
L[i] = add_and({a[i], pref[i - 1]});
}
R[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; --i) {
R[i] = add_and({a[i], suf[i + 1]});
}
cerr << "LR = " << endl;
output(all(L));
output(all(R));
return diff(R, L);
}
int n, m, k;
int get(int r, int c) {
return r * m + c;
}
void construct_network(int _n, int _m, int _k) {
n = _n;
m = _m;
k = _k;
ONE = add_or({0, add_not(0)});
ZERO = add_and({0, add_not(0)});
vector<int> rows, columns;
for (int i = 0; i < n; ++i) {
vector<int> cur_row;
for (int j = 0; j < m; ++j) {
cur_row.push_back(get(i, j));
}
rows.push_back(add_or(cur_row));
}
for (int i = 0; i < m; ++i) {
vector<int> cur_column;
for (int j = 0; j < n; ++j) {
cur_column.push_back(get(j, i));
}
columns.push_back(add_or(cur_column));
}
// cerr << "rows" << endl;
// output(all(rows));
// cerr << "columns" << endl;
// output(all(columns));
vector<int> row_d = diff(rows);
vector<int> col_d = diff(columns);
// cerr << "row_d" << endl;
// output(all(row_d));
// cerr << "col_d" << endl;
// output(all(col_d));
vector<int> poss;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i + j == k) {
poss.push_back(add_and({row_d[i], col_d[j]}));
}
}
}
add_or(poss);
}
Compilation message
vision.cpp: In function 'std::vector<int> to_number(const std::vector<int>&, int)':
vision.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < A.size(); ++i) {
| ~~^~~~~~~~~~
vision.cpp: In function 'void flip(std::vector<int>&)':
vision.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < a.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
640 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
512 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
1532 KB |
on inputs (80, 199), (81, 199), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
