#include "paint.h" #include <cassert> #include <cstdio> #include <string> #include <vector> #include <bits/stdc++.h> using namespace std; using ll = long long; const ll N = 3e5 + 5; const ll INF = 1e9 + 5; const ll MOD = 998244353; int dp[N], ch[N], ans = 0; vector<vector<ll>> v(N); void calc(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { vector<int> cord; for(int i = 0; i <= N - M; i++) { int ok = 0; for(auto x : v[C[i]]) { int need = M - 1, worker = (x + 1) % M, cur = i + 1, curok = 1; while(need) { int id = lower_bound(v[C[cur]].begin(), v[C[cur]].end(), worker) - v[C[cur]].begin(); if(id < v[C[cur]].size() && v[C[cur]][id] == worker) { need--; worker = (worker + 1) % M; cur++; } else { curok = 0; break; } } ok |= curok; if(ok) { break; } } if(ok) { cord.push_back(i); } } ll l = 0, r = 0, sum = 0, can = 1; while(true) { int id = upper_bound(cord.begin(), cord.end(), r) - cord.begin(); if(id != 0) { id--; if(cord[id] + M <= r) { ans = -1; can = 0; break; } r = cord[id] + M; l = cord[id] + 1; sum++; if(r >= N) { break; } } else { ans = -1; can = 0; break; } } if(can) { ans = sum; } } int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { for(int i = 0; i < M; i++) { for(int j = 0; j < A[i]; j++) { v[B[i][j]].push_back(i); } } for(int i = 0; i < K; i++) { sort(v[i].begin(), v[i].end()); } calc(N, M, K, C, A, B); for(int i = 0; i < K; i++) v[i].clear(); for(int i = 0; i < N; i++) ch[i] = dp[i] = 0; return ans; } // 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; // }