Submission #146336

#TimeUsernameProblemLanguageResultExecution timeMemory
146336jwvg0425Vision Program (IOI19_vision)C++17
0 / 100
11 ms1264 KiB
#include "vision.h" #include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; int h, w, k; int cell(int x, int y) { return y * w + x; } vector<int> allXCell(int y) { vector<int> xs; for (int x = 0; x < w; x++) xs.push_back(cell(x, y)); return xs; } vector<int> allYCell(int x) { vector<int> ys; for (int y = 0; y < h; y++) ys.push_back(cell(x, y)); return ys; } vector<int> range(int s, int e) { vector<int> v; for (int i = s; i <= e; i++) v.push_back(i); return v; } int xcell(int x) { return h * w + x; } int ycell(int y) { return h * w + w + y; } int xd[205]; int yd[205]; void brute() { int inst = 0; for (int y1 = 0; y1 < h; y1++) { for (int x1 = 0; x1 < w; x1++) { int a = y1 * w + x1; for (int y2 = 0; y2 < h; y2++) { for (int x2 = 0; x2 < w; x2++) { if (abs(x1 - x2) + abs(y1 - y2) != k) continue; int b = y2 * w + x2; add_and({ a, b }); inst++; } } } } vector<int> ors; for (int i = 0; i < inst; i++) ors.push_back(h * w + i); add_or(ors); } void construct_network(int H, int W, int K) { if (min(H, W) == 1) { brute(); return; } memset(xd, -1, sizeof(xd)); memset(yd, -1, sizeof(yd)); h = H; w = W; k = K; for (int x = 0; x < W; x++) add_or(allYCell(x)); for (int y = 0; y < H; y++) add_or(allXCell(y)); xd[0] = add_xor(range(xcell(0), xcell(w - 1))); // x1 == x2 검사 셀 yd[0] = add_xor(range(ycell(0), ycell(h - 1))); // y1 == y2 검사 셀 for (int d = 1; d <= min(k, W - 1); d++) { vector<int> c; for (int x = 0; x < W - d; x++) c.push_back(add_and({ xcell(x), xcell(x + d) })); xd[d] = add_or(c); } for (int d = 1; d <= min(k, H - 1); d++) { vector<int> c; for (int y = 0; y < H - d; y++) c.push_back(add_and({ ycell(y), ycell(y + d) })); yd[d] = add_or(c); } vector<int> check; for (int xk = 0; xk <= k; xk++) { int yk = k - xk; if (xd[xk] == -1 || yd[yk] == -1) continue; check.push_back(add_and({ xd[xk], yd[yk] })); } add_or(check); }
#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...