#include "paint.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; unordered_map<int, int> mp[100100]; bool visited[707]; int minimumInstructions( int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { vector<vector<int>> D(K); for (int i=0;i<M;i++){ for (int j=0;j<(int)B[i].size();j++){ D[B[i][j]].push_back(i); mp[B[i][j]][i] = (int)D[B[i][j]].size()-1; } } vector<pair<int, int>> v, tmp; vector<bool> chk(N); for (int i=0;i<N;i++){ for (auto &p:v){ if (p.second>=M) chk[i-M] = 1; int tmp2 = p.first+1; if (tmp2==M) tmp2 = 0; auto iter = mp[C[i]].find(tmp2); if (iter!=mp[C[i]].end()){ tmp.emplace_back(tmp2, p.second+1); visited[iter->second] = 1; } } if (i<=N-M+1){ for (int j=0;j<(int)D[C[i]].size();j++) if (!visited[j]){ tmp.emplace_back(D[C[i]][j], 1); }} swap(v, tmp); tmp.clear(); memset(visited, 0, sizeof(visited)); /*printf("%d: ", i); for (auto &p:v) printf("(%d, %d) ", p.first, p.second); printf("\n");*/ } for (auto &p:v) if (p.second>=M) chk[N-M] = 1; //for (int i=0;i<N;i++) printf("%d ", (int)chk[i]); //printf("\n"); int prv = 0, nxt = -1, cur = 0, cnt = 0; while(prv<N){ bool flag = 0; for (int i=cur;i<=prv;i++) if (chk[i]){ nxt = i+M; flag = 1; } if (!flag) break; cnt++; cur = prv+1; prv = nxt; } if (prv<N) return -1; return cnt; }