#include "paint.h" #include <cstring> #include <vector> const int N = 20000, K = 100000, M = 2000; int min(int a, int b) { return a < b ? a : b; } int minimumInstructions(int n, int m, int k, std::vector<int> aa, std::vector<int> kk, std::vector<std::vector<int>> aaa) { int h, i, i_, j, ans; if (n <= 500) { static int jj[K][M], ll[K], len[N][M]; static char can[N]; for (j = 0; j < m; j++) for (h = 0; h < kk[j]; h++) { int a = aaa[j][h]; jj[a][ll[a]++] = j; } for (i = 0; i < n; i++) { int a = aa[i]; for (h = 0; h < ll[a]; h++) len[i][(jj[a][h] - i % m + m) % m] = 1; } for (j = 0; j < m; j++) for (i = n - 2; i >= 0; i--) if (len[i][j]) len[i][j] += len[i + 1][j]; for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (len[i][j] >= m) { can[i] = 1; break; } if (!can[0]) return -1; i = 0, ans = 1; while (i + m < n) { for (i_ = min(i + m, n - 1); i_ > i; i_--) if (can[i_]) break; if (i_ == i) return -1; i = i_, ans++; } return ans; } else { static int jj[K]; memset(jj, -1, k * sizeof *jj); for (j = 0; j < m; j++) for (h = 0; h < kk[j]; h++) jj[aaa[j][h]] = j; for (i = 0; i < n; i++) if (jj[aa[i]] == -1) return -1; ans = 0; for (i = 0; i < n; i = i_) { i_ = i + 1; while (i_ < n && (jj[aa[i_ - 1]] + 1) % m == jj[aa[i_]]) i_++; if (i_ - i < m) return -1; ans += (i_ - i + m - 1) / m; } } return ans; }