Submission #982384

#TimeUsernameProblemLanguageResultExecution timeMemory
982384vjudge1Painting Walls (APIO20_paint)C++17
0 / 100
0 ms344 KiB
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #include <x86intrin.h> #include <bits/stdc++.h> #include <chrono> #include <random> // @author: Vlapos namespace operators { template <typename T1, typename T2> std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x) { in >> x.first >> x.second; return in; } template <typename T1, typename T2> std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x) { out << x.first << " " << x.second; return out; } template <typename T1> std::istream &operator>>(std::istream &in, std::vector<T1> &x) { for (auto &i : x) in >> i; return in; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::vector<T1> &x) { for (auto &i : x) out << i << " "; return out; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::set<T1> &x) { for (auto &i : x) out << i << " "; return out; } } // name spaces using namespace std; using namespace operators; // end of name spaces // defines #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define f first #define s second #define uint unsigned int #define all(vc) vc.begin(), vc.end() // end of defines // usefull stuff void boost() { ios_base ::sync_with_stdio(false); cin.tie(0); cout.tie(0); } inline int getbit(int &x, int &bt) { return (x >> bt) & 1; } const int dx4[4] = {-1, 0, 0, 1}; const int dy4[4] = {0, -1, 1, 0}; const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1}; const ll INF = (1e18) + 500; const int BIG = (1e9) * 2 + 100; const int MAXN = (1e5) + 5; const int MOD7 = (1e9) + 7; const int MOD9 = (1e9) + 9; const uint MODFFT = 998244353; int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { int n = N, m = M, k = K; vector<vector<int>> col(k); map<pii, bool> good; for (int i = 0; i < m; ++i) for (auto el : B[i]) { col[el].pb(i); good[{i, el}]; } vector<int> isGood(n); map<int, int> isAdded; vector<pii> els; for (int i = 0; i < n; ++i) { vector<pii> nels; int curMaxLen = 0; for (auto [el, len] : els) { if (good.find({(el + 1) % m, C[i]}) != good.end()) { nels.pb({(el + 1) % m, len + 1}); curMaxLen = max(curMaxLen, len + 1); } else isAdded[el] = 0; } swap(nels, els); for (auto el : col[C[i]]) if (!isAdded[el]) { isAdded[el] = 1; els.pb({el, 1}); curMaxLen = max(curMaxLen, 1); } if (curMaxLen >= m) isGood[i - m + 1] = 1; } int pr = 0; int curDone = 0; int cnt = 0; while (curDone < n - 1) { int curMax = -1; for (int i = pr; i <= curDone; ++i) if (isGood[i]) curMax = i; if (curMax == -1) break; cnt++; pr = curDone + 1; curDone = curMax + m; } if (curDone < n - 1) return -1; else return cnt; } // //////////////////////////// // #include "paint.h" // #include <cassert> // #include <cstdio> // #include <string> // #include <vector> // int main() // { // int N, M, K; // assert(3 == scanf("%d %d %d", &N, &M, &K)); // std::vector<int> C(N); // for (int i = 0; i < N; ++i) // { // assert(1 == scanf("%d", &C[i])); // } // std::vector<int> A(M); // std::vector<std::vector<int>> B(M); // for (int i = 0; i < M; ++i) // { // assert(1 == scanf("%d", &A[i])); // B[i].resize(A[i]); // for (int j = 0; j < A[i]; ++j) // { // assert(1 == scanf("%d", &B[i][j])); // } // } // int minimum_instructions = minimumInstructions(N, M, K, C, A, B); // printf("%d\n", minimum_instructions); // return 0; // }
#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...