#include "paint.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; 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); } } vector<pair<int, int>> v, tmp; vector<bool> chk(N); for (int i=0;i<N;i++){ vector<bool> visited(D[C[i]].size()); for (auto &p:v){ if (p.second>=M) chk[i-M] = 1; int tmp2 = p.first+1; if (tmp2==M) tmp2 = 0; auto iter = lower_bound(D[C[i]].begin(), D[C[i]].end(), tmp2); if (iter!=D[C[i]].end() && *iter==tmp2){ tmp.emplace_back(tmp2, p.second+1); visited[iter-D[C[i]].begin()] = 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(); /*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; }