제출 #727661

#제출 시각아이디문제언어결과실행 시간메모리
727661PixelCatVision Program (IOI19_vision)C++14
59 / 100
12 ms2128 KiB
#include "vision.h" #ifdef NYAOWO #include "grader.cpp" #endif #include <bits/stdc++.h> #define For(i, a, b) for(int i = a; i <= b; i++) #define Forr(i,a, b) for(int i = a; i >= b; i--) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define eb emplace_back // #define int LL using namespace std; using LL = long long; using pii = pair<int, int>; const int MAXN = 410; const int LG = 9; int get_xor(int *x, int l, int r) { if(l == 0) return x[r]; return add_xor({x[r], x[l - 1]}); } int get_or(int x[MAXN][LG], int l, int r) { int k = __lg(r - l + 1); return add_or({x[l][k], x[r - (1 << k) + 1][k]}); // vector<int> v; // For(i, l, r) v.eb(x[i]); // return add_or(v); } vector<vector<int>> dia1; // x + y, [0, H + W - 2] vector<vector<int>> dia2; // x - y + W - 1, [0, H + W - 2] int xor1[MAXN], xor2[MAXN]; int or1[MAXN][LG], or2[MAXN][LG]; int check(int k) { int n = sz(dia1); vector<int> v; For(i, 0, n - k - 1) { // or = 1, xor = 0 => 2 black cells v.eb(add_xor({ get_or(or1, i, i + k), get_xor(xor1, i, i + k) })); } int a = add_or(v); v.clear(); For(i, 0, n - k - 1) { // or = 1, xor = 0 => 2 black cells v.eb(add_xor({ get_or(or2, i, i + k), get_xor(xor2, i, i + k) })); } int b = add_or(v); return add_and({a, b}); } void construct_network(int H, int W, int K) { // 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); int n = H + W - 1; dia1.resize(n); dia2.resize(n); For(i, 0, H - 1) For(j, 0, W - 1) { int id = i * W + j; dia1[i + j].eb(id); dia2[i - j + W - 1].eb(id); } xor1[0] = add_xor(dia1[0]); xor2[0] = add_xor(dia2[0]); For(i, 1, n - 1) { dia1[i].eb(xor1[i - 1]); xor1[i] = add_xor(dia1[i]); dia1[i].pop_back(); dia2[i].eb(xor2[i - 1]); xor2[i] = add_xor(dia2[i]); dia2[i].pop_back(); } For(i, 0, n - 1) { or1[i][0] = add_or(dia1[i]); or2[i][0] = add_or(dia2[i]); } For(j, 0, LG - 2) For(i, 0, n - 1) { or1[i][j + 1] = or1[i][j]; or2[i][j + 1] = or2[i][j]; if(i + (1 << j) < n) { or1[i][j + 1] = add_or({or1[i][j], or1[i + (1 << j)][j]}); or2[i][j + 1] = add_or({or2[i][j], or2[i + (1 << j)][j]}); } } int a = check(K); int b = check(K - 1); b = add_not(b); add_and({a, b}); }
#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...