// AM+DG
/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "vision.h"
int cellnum(int r, int c, int W) {
return r * W + c;
}
void construct_network(int h, int w, int k) {
// Falsy/truthy values, may help!
int falsy = add_xor({0, 0});
int truthy = add_not(falsy);
// Row/col stuff
vi row_has;
LI(i, 0, h) {
vi all_in_row;
LI(j, 0, w) {
all_in_row.pb(cellnum(i, j, w));
}
row_has.pb(add_or(all_in_row));
}
vi col_has;
LI(i, 0, w) {
vi all_in_col;
LI(j, 0, h) all_in_col.pb(cellnum(j, i, w));
col_has.pb(add_or(all_in_col));
}
// int row_is_same = add_xor(row_has);
// int col_is_same = add_xor(col_has);
// dist_from_orig[i] should OR all points that satisfy x + y = i
vi dist_from_orig;
LI(i, 0, h + w - 1) {
vi all_in_diag;
LI(x, 0, w) {
int y = i - x;
if(y < 0 || y >= h) continue;
all_in_diag.pb(cellnum(y, x, w));
}
assert((int)all_in_diag.size() > 0);
dist_from_orig.pb(add_or(all_in_diag));
}
// dist_from_p2[i] should OR all points that satisfy W - 1 - x + y = i -> y - x = i - W + 1 -> y = x + i - w + 1
vi dist_from_p2;
LI(i, 0, h + w - 1) {
vi all_in_diag;
LI(x, 0, w) {
int y = i + x - w + 1;
if(y < 0 || y >= h) continue;
all_in_diag.pb(cellnum(y, x, w));
}
assert((int)all_in_diag.size() > 0);
dist_from_p2.pb(add_or(all_in_diag));
}
// Next step: determine whether the precondition for necessary condition 1 is true
// Necessary condition 1: the horizontal and vertical distances must both be no more than k
/// To do this, we can create "sliding windows". Over these sliding windows, we compute the "or" and "xor"
/// If the "or" is 1 and the "xor" is 0 for any of the sliding windows, we know that the two points are within that sliding window and thus have a separation of no more than k
int r_is_bounded;
if(k < h) {
vi nc1r;
LI(i, 0, h - k) {
// In the current window, we will consider the range [i, i + k]
vi window;
LI(j, i, i + k + 1) {
window.pb(row_has[j]);
}
int cur_or = add_or(window);
int cur_xor = add_xor(window);
int is_contained = add_and({cur_or, add_not(cur_xor)});
nc1r.pb(is_contained);
}
r_is_bounded = add_or(nc1r);
} else {
r_is_bounded = truthy;
}
int c_is_bounded;
if(k < w) {
vi nc1c;
LI(i, 0, w - k) {
// In the current window, we will consider the range [i, i + k]
vi window;
LI(j, i, i + k + 1) {
window.pb(col_has[j]);
}
int cur_or = add_or(window);
int cur_xor = add_xor(window);
int is_contained = add_and({cur_or, add_not(cur_xor)});
nc1c.pb(is_contained);
}
c_is_bounded = add_or(nc1c);
} else {
c_is_bounded = truthy;
}
int oned_is_bounded = add_and({r_is_bounded, c_is_bounded});
// Next step: determine whether the precondition for necessary condition 2 is true
// Necessary condition 2: either the top-right diagonal distance is k or the top-left diagonal distance is k
vi dist_orig_k_sep;
LI(i, 0, h + w - 1 - k) {
dist_orig_k_sep.pb(add_and({dist_from_orig[i], dist_from_orig[i + k]}));
}
assert((int)dist_orig_k_sep.size() > 0);
int dist_orig_is_k_sep = add_or(dist_orig_k_sep);
vi dist_p2_k_sep;
LI(i, 0, h + w - 1 - k) {
dist_p2_k_sep.pb(add_and({dist_from_p2[i], dist_from_p2[i + k]}));
}
assert((int)dist_p2_k_sep.size() > 0);
int dist_p2_is_k_sep = add_or(dist_p2_k_sep);
int dist_diag_is_k_sep = add_or({dist_orig_is_k_sep, dist_p2_is_k_sep});
// Next step: determine whether both necessary conditions are true. This is the answer
int yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit = add_and({oned_is_bounded, dist_diag_is_k_sep});
return;
}
Compilation message
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:154:9: warning: unused variable 'yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit' [-Wunused-variable]
154 | int yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit = add_and({oned_is_bounded, dist_diag_is_k_sep});
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
676 KB |
Output is correct |
| 3 |
Correct |
4 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
432 KB |
Output is correct |
| 6 |
Correct |
3 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
436 KB |
Output is correct |
| 11 |
Correct |
2 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
436 KB |
Output is correct |
| 17 |
Correct |
2 ms |
600 KB |
Output is correct |
| 18 |
Correct |
2 ms |
856 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| 21 |
Correct |
0 ms |
344 KB |
Output is correct |
| 22 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
11 ms |
2140 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 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
