#include "vision.h"
#include <vector>
#include <cassert>
using namespace std;
const int NMAX = 800;
const int CT = 400;
int _H, _W;
int Get_Index(int x, int y) {
return x * _W + y;
}
vector<int> diagPlus[NMAX + 5], diagMinus[NMAX + 5];
int resDiagPlus[NMAX + 5], resDiagMinus[NMAX + 5];
int prefPlus[NMAX + 5], sufPlus[NMAX + 5];
int prefMinus[NMAX + 5], sufMinus[NMAX + 5];
void construct_network(int H, int W, int K) {
_H = H;
_W = W;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) {
diagPlus[i + j].push_back(Get_Index(i, j));
diagMinus[i - j + CT].push_back(Get_Index(i, j));
}
///DiagPlus
for (int i = 0; i <= H + W; i++)
if ((int) diagPlus[i].size() > 0) {
vector<int> Ns;
for (auto it : diagPlus[i])
Ns.push_back(it);
assert((int)Ns.size() > 0);
resDiagPlus[i] = add_or(Ns);
}
///DiagMinus
for (int i = -W; i <= H; i++)
if ((int) diagMinus[i + CT].size() > 0) {
vector<int> Ns;
for (auto it : diagMinus[i + CT])
Ns.push_back(it);
assert((int)Ns.size() > 0);
resDiagMinus[i + CT] = add_or(Ns);
}
///DiagPlus L->R
for (int i = 0; i <= H + W; i++)
if ((int) diagPlus[i].size() > 0) {
///Prefix OR 0...i
vector<int> Ns;
for (int j = 0; j <= i; j++) {
Ns.push_back(resDiagPlus[j]);
}
assert((int)Ns.size() > 0);
prefPlus[i] = add_or(Ns);
}
///DiagPlus R->L
for (int i = H + W - 2; i >= 0; i--) {
///Suffix OR i...H+W-2
vector<int> Ns;
for (int j = i; j <= H + W - 2; j++) {
Ns.push_back(resDiagPlus[j]);
}
assert((int)Ns.size() > 0);
sufPlus[i] = add_or(Ns);
}
///DiagMinus L->R
for (int i = -W + 1; i <= H - 1; i++) {
///Prefix OR -W+1...i
vector<int> Ns;
for (int j = -W + 1; j <= i; j++) {
Ns.push_back(resDiagMinus[j + CT]);
}
assert((int)Ns.size() > 0);
prefMinus[i + CT] = add_or(Ns);
}
///DiagMinus R->L
for (int i = H - 1; i >= -W + 1; i--) {
///Suffix OR i...H-1
vector<int> Ns;
for (int j = i; j <= H - 1; j++) {
Ns.push_back(resDiagMinus[j + CT]);
}
assert((int)Ns.size() > 0);
sufMinus[i + CT] = add_or(Ns);
}
///CASE 1: diagPlus is 1 at a distance of K and diagMinus is 1 at a distance of at most K
///CODE HERE...
int res1 = -1;
vector<int> resAnds;
for (int i = 0; i <= W + H - 2 - K; i++) {
vector<int> Ns;
Ns.push_back(resDiagPlus[i]);
Ns.push_back(resDiagPlus[i + K]);
resAnds.push_back(add_and(Ns));
}
assert((int)resAnds.size() > 0);
int isDiagPlusAtDistanceK = add_or(resAnds);
resAnds.clear();
for (int l = -W + 1; l <= H - 1 - K; l++) {
vector<int> Ns;
if (l - 1 >= -W + 1) {
Ns.push_back(prefMinus[l - 1 + CT]);
}
if (l + K + 1 <= H - 1) {
Ns.push_back(sufMinus[l + K + 1 + CT]);
}
if ((int) Ns.size() > 0) {
int fsp = add_or(Ns);
resAnds.push_back(add_not(fsp));
}
}
assert((int)resAnds.size() > 0);
int isDiagMinusAtDistanceAtMostK = add_or(resAnds);
res1 = add_and({isDiagPlusAtDistanceK, isDiagMinusAtDistanceAtMostK});
///CASE 2: diagMinus is 1 at a distance of K and diagPlus is 1 at a distance of at most K
///CODE HERE...
int res2 = -1;
resAnds.clear();
for (int i = -W + 1; i <= H - 1 - K; i++) {
vector<int> Ns;
Ns.push_back(resDiagMinus[i + CT]);
Ns.push_back(resDiagMinus[i + K + CT]);
resAnds.push_back(add_and(Ns));
}
assert((int)resAnds.size() > 0);
int isDiagMinusAtDistanceK = add_or(resAnds);
resAnds.clear();
for (int l = 0; l <= H + W - 2 - K; l++) {
vector<int> Ns;
if (l - 1 >= 0) {
Ns.push_back(prefPlus[l - 1]);
}
if (l + K + 1 <= H + W - 2) {
Ns.push_back(sufPlus[l + K + 1]);
}
if ((int) Ns.size() > 0) {
int fsp = add_or(Ns);
resAnds.push_back(add_not(fsp));
}
}
assert((int)resAnds.size() > 0);
int isDiagPlusAtDistanceAtMostK = add_or(resAnds);;
res2 = add_and({isDiagMinusAtDistanceK, isDiagPlusAtDistanceAtMostK});
add_or({res1, res2});
/*
std::vector<int> Ns;
Ns = {0, 1};
int a = add_and(Ns);
Ns = {0, a};
int b = add_or(Ns);
Ns = {0, 1, b};
int c = add_xor(Ns);
add_not(c);
*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1132 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
1388 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
5132 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
7 ms |
876 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1260 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1260 KB |
Output is correct |
| 7 |
Correct |
26 ms |
3052 KB |
Output is correct |
| 8 |
Correct |
26 ms |
3052 KB |
Output is correct |
| 9 |
Correct |
48 ms |
5224 KB |
Output is correct |
| 10 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
