제출 #571629

#제출 시각아이디문제언어결과실행 시간메모리
571629SlavicG벽 칠하기 (APIO20_paint)C++17
0 / 100
1 ms212 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(),v.rend() #define pb push_back #define sz(a) (int)a.size() const int K = 16; int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) { vector<int> p[k + 1]; map<int, int> st[n + 1][K]; for(int i = 0; i < m; ++i) { for(auto x: b[i]) { p[x].pb(i); } } for(int i = 0; i < n; ++i) { for(auto x: p[c[i]]) { st[x][i][0] = 1; } } for(int j = 1; j < K; ++j) { for(int i = 0; i + (1 << j) <= m && i + (1 << j) <= n; ++i) { for(auto x: p[c[i]]) { if(st[x][i][j - 1] && st[(x + (1 << j)) % m][i + (1 << j)][j - 1]) { st[x][i][j] = 1; } } } } vector<bool> can(n, false); for(int i = 0; i + m - 1 < n; ++i) { for(auto x: p[c[i]]) { int cur = x; int idx = i; bool ok = true; for(int j = 0; j < K; ++j) { if(m & (1 << j)) { if(!st[cur][idx][j]) { ok = false; break; } cur = (cur + (1 << j)) % m; assert(idx <= n); idx += (1 << j); } } if(ok) { can[i] = true; break; } } } set<int> good; forn(i, n) if(can[i]) good.insert(i); int lst = -1e9, ans = 0; for(int i = 0; i < n; ++i) { if(lst + m - 1 >= i) continue; ++ans; if(can[i]) { lst = i; } else { auto it = good.lower_bound(i); if(it == good.begin()) return -1; --it; if(*it + m - 1 < i) return -1; lst = *it; } } return ans; } /* void solve() { } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; //cin >> t; while(t--) { solve(); } } */
#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...