Submission #1244069

#TimeUsernameProblemLanguageResultExecution timeMemory
1244069DedibeatVision Program (IOI19_vision)C++20
47 / 100
5 ms1096 KiB
#include "vision.h" #include<bits/stdc++.h> using namespace std; using ll = long long; #define F first #define S second #define all(x) (x).begin(), (x).end() template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "(" << p.F << "," << p.S << ")"; } template<typename T> void print(const T &v, int lim = 1e9) { for(auto x : v) if(lim-- > 0) cout << x << " "; cout << endl; } template<typename T> void print(T *begin, const T *end) { for(T *it = begin; it < end; it++) cout << *it << " "; cout << endl; } int n, m, k; inline int idx(int x, int y) { return x * m + y; } void brute() { vector<pair<int, int>> pairs; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { for(int x = 0; x <= k; x++) { int y = k - x; if(i + x < n && j + y < m) pairs.emplace_back(idx(i, j), idx(i + x, j + y)); if(i + x < n && j - y >= 0) pairs.emplace_back(idx(i, j), idx(i + x, j - y)); } } } vector<int> v; int j = n * m; for(auto [idx1, idx2] : pairs) { add_and({idx1, idx2}); v.push_back(j++); } add_or(v); } void sol1() { vector<int> rows, cols, row_adj, col_adj; int it = n * m; for(int i = 0; i < n; i++) { vector<int> v; for(int j = 0; j < m; j++) v.push_back(idx(i, j)); add_or(v); rows.push_back(it++); } for(int j = 0; j < m; j++) { vector<int> v; for(int i = 0; i < n; i++) v.push_back(idx(i, j)); add_or(v); cols.push_back(it++); } for(int i = 0; i < n - 1; i++) { add_and({rows[i], rows[i + 1]}); row_adj.push_back(it++); } for(int i = 0; i < m - 1; i++) { add_and({cols[i], cols[i + 1]}); col_adj.push_back(it++); } int cond1, cond2; add_or(row_adj); add_xor(cols); add_and({it, it + 1}); cond1 = it + 2; it += 3; add_or(col_adj); add_xor(rows); add_and({it, it + 1}); cond2 = it + 2; it += 3; add_or({cond1, cond2}); } void smart() { vector<int> rows, cols; int it = n * m; for(int i = 0; i < n; i++) { vector<int> v; for(int j = 0; j < m; j++) v.push_back(idx(i, j)); add_or(v); rows.push_back(it++); } for(int j = 0; j < m; j++) { vector<int> v; for(int i = 0; i < n; i++) v.push_back(idx(i, j)); add_or(v); cols.push_back(it++); } vector<int> dif_row(k + 1), dif_col(k + 1); for(int dif = 1; dif <= k; dif++) { vector<int> v; for(int i = 0; i + dif < n; i++) { add_and({rows[i], rows[i + dif]}); v.push_back(it++); } add_or(v); dif_row[dif] = it++; v.clear(); for(int j = 0; j + dif < m; j++) { add_and({cols[j], cols[j + dif]}); v.push_back(it++); } add_or(v); dif_col[dif] = it++; } add_xor(rows); dif_row[0] = it++; add_xor(cols); dif_col[0] = it++; vector<int> conds; for(int x = 0; x <= k; x++) { add_and({dif_row[x], dif_col[k - x]}); conds.push_back(it++); } add_or(conds); } void construct_network(int H, int W, int K) { n = H, m = W, k = K; if(max(n, m) <= 10 || min(n, m) == 1) brute(); else if(k == 1) sol1(); else smart(); }
#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...