Submission #617788

#TimeUsernameProblemLanguageResultExecution timeMemory
617788lorenzoferrariVision Program (IOI19_vision)C++17
52 / 100
1 ms340 KiB
#include "vision.h" #include <vector> #include <cassert> using namespace std; void subtask5(int h, int w, int k) { int l = h*w; int r = l; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { for (int ii = i; ii < h; ++ii) for (int jj = 0; jj < w; ++jj) { if (abs(i-ii) + abs(j-jj) != k) continue; vector<int> q; q.push_back(i*w + j); q.push_back(ii*w + jj); r = add_and(q); } } vector<int> q; for (int i = l; i <= r; ++i) { q.push_back(i); } add_or(q); } void subtask6(int h, int w, int k) { // 0,0 is black vector<int> tor; for (int i = 0; i <= k; ++i) { int j = k - i; if (!(0 <= i && i < h)) continue; if (!(0 <= j && j < w)) continue; tor.push_back(add_and({0, i*w+j})); } add_or(tor); } void construct_network(int h, int w, int k) { if (min(h, w) == 1) { subtask5(h, w, k); return; } else if (max(h, w) > 30) { subtask6(h, w, k); return; } int tid = add_or({0, add_not(0)}); int fid = add_not(tid); vector<int> rows(h); vector<int> cols(w); for (int i = 0; i < h; ++i) { vector<int> q; for (int j = 0; j < w; ++j) { q.push_back(i*w + j); } rows[i] = add_or(q); } for (int j = 0; j < w; ++j) { vector<int> q; for (int i = 0; i < h; ++i) { q.push_back(i*w + j); } cols[j] = add_or(q); } auto add_fixed = [&](vector<int> v, int d) -> int { assert(0 < d && d < (int)v.size()); vector<int> tor; for (int i = 0; i + d < (int)v.size(); ++i) { tor.push_back(add_and({v[i], v[i+d]})); } return add_or(tor); }; vector<int> dh(h); vector<int> dw(w); for (int i = 1; i < h; ++i) dh[i] = add_fixed(rows, i); for (int i = 1; i < w; ++i) dw[i] = add_fixed(cols, i); vector<int> nh(1,tid); vector<int> nw(1,tid); for (int i = 1; i < h; ++i) nh.push_back(add_not(dh[i])); for (int i = 1; i < w; ++i) nw.push_back(add_not(dw[i])); dh[0] = add_and(nh); dw[0] = add_and(nw); vector<int> tor(1, fid); for (int i = 0; i < h; ++i) { int j = k - i; if (0 <= j && j < w) { tor.push_back(add_and({dh[i], dw[j]})); } } add_or(tor); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...