#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}
template<bool enabled>
struct Debug{
template<typename S, typename T = void> struct Tag_Printable : false_type {};
template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
template<typename S, typename T = void> struct Tag_Iterable: false_type {};
template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};
template<typename T, typename... Args>
Debug& print(T const&x, true_type, Args...){
#ifdef LOCAL_RUN
if(enabled){
cerr << boolalpha << x;
}
#endif // LOCAL_RUN
return *this;
}
template<typename T>
Debug& print(T const&x, false_type, true_type){
*this << "[";
bool first = true;
for(auto &e:x){
if(!first) *this << ", ";
*this << e;
first = false;
}
return *this << "]";
}
template<typename S, typename T>
Debug& print(pair<S, T> const&x, false_type, false_type){
return *this << "(" << x.first << ", " << x.second << ")";
}
template<typename T>
Debug& operator<<(T const&x){
return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
}
};
Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " << x
const int m = __lg(400)+1;
const int ZERO = -1, ONE = -2;
void remove_consts(vector<int> &v){
v.erase(partition(v.begin(), v.end(), [&](int const&a){return a>=0;}), v.end());
}
int better_and(vector<int> v){
for(auto const&e:v){
if(e==ZERO) return ZERO;
}
remove_consts(v);
if(v.empty()) return ONE;
return add_and(v);
}
int better_or(vector<int> v){
for(auto const&e:v){
if(e==ONE) return ONE;
}
remove_consts(v);
if(v.empty()) return ZERO;
return add_or(v);
}
int better_xor(vector<int> v){
int flips = 0;
for(auto const&e:v){
if(e==ONE) return ++flips;
}
remove_consts(v);
if(v.empty()) return flips ? ONE : ZERO;
return flips%2 ? add_not(add_xor(v)) : add_xor(v);
}
int better_not(int a){
return a==ONE ? ZERO : a==ZERO ? ONE : add_not(a);
}
#define add_not better_not
#define add_or better_or
#define add_and better_and
#define add_xor better_xor
int add_majority(int a, int b, int c){
return add_or({add_and({a, b}), add_and({b, c}), add_and({c, a})});
}
vector<int> build_adder(vector<int> v, vector<int> w){
assert(v.size() == w.size());
const int n = v.size();
vector<int> ret(n);
ret[0] = add_xor({v[0], w[0]});
int carry = add_and({v[0], w[0]});
for(int i=1;i<n;++i){
ret[i] = add_xor({v[i], w[i], carry});
carry = add_majority(v[i], w[i], carry);
}
//ret[n] = carry;
return ret;
}
vector<int> build_bits(vector<int> v){
const int n = v.size();
vector<int> ret(m, ZERO);
for(int j=0;j<m;++j){
vector<int> tmp;
for(int i=0;i<n;++i){
if((i>>j)&1) tmp.push_back(v[i]);
}
ret[j] = add_or(tmp);
}
debug << "Bits: " << ret << "\n";
return ret;
}
array<vector<int>, 2> first_last(vector<int> a){
const int n = a.size();
array<vector<int>, 2> ret{};
for(auto &e:ret) e.resize(n);
for(int i=0;i<n;++i){
vector<int> tmp;
for(int j=0;j<i;++j){
tmp.push_back(a[j]);
}
ret[0][i] = add_and({a[i], add_not(add_or(tmp))});
}
for(int i=0;i<n;++i){
vector<int> tmp;
for(int j=i+1;j<n;++j){
tmp.push_back(a[j]);
}
ret[1][i] = add_and({a[i], add_not(add_or(tmp))});
}
return ret;
}
vector<int> sub(vector<int> a, vector<int> b){
for(auto &e:b) e = add_not(e);
vector<int> one(a.size(), ZERO);
one[0] = ONE;
return build_adder(a, build_adder(b, one));
}
void construct_network(int H, int W, int K) {
const int X = H, Y = W;
auto ind = [&](int x, int y){
assert(0 <= x && x < X);
assert(0 <= y && y < Y);
return x*Y+y;
};
vector<int> rows(X), cols(Y);
for(int i=0;i<X;++i){
vector<int> tmp;
for(int j=0;j<Y;++j){
tmp.push_back(ind(i, j));
}
rows[i] = add_xor(tmp);
}
for(int j=0;j<Y;++j){
vector<int> tmp;
for(int i=0;i<X;++i){
tmp.push_back(ind(i, j));
}
cols[j] = add_xor(tmp);
}
auto R = first_last(rows);
auto C = first_last(cols);
vector<int> dx = sub(build_bits(R[1]), build_bits(R[0]));
vector<int> dy = sub(build_bits(C[1]), build_bits(C[0]));
vector<int> d = build_adder(dx, dy);
debug << dx << " " << dy << "\n";
for(int i=0;i<(int)d.size();++i){
if((~K>>i)&1){
d[i] = add_not(d[i]);
}
}
debug << named(d) << "\n";
int ret = add_and(d);
assert(ret >= 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 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 |
2 ms |
256 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 |
2 ms |
256 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 |
2 ms |
256 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 |
7 ms |
760 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 |
2 ms |
256 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 |
21 ms |
2040 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 |
2 ms |
256 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
