#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100010;
vector<int> col2con[N];
set<int> con2col[N];
int res[N];
int lst_nonmatch[N];
int interval_match[N];
int cnt_seg, cnt_con, cnt_col;
int find_nonmatch(int seg, int con)
{
int mod = (con - seg) % cnt_con;
mod = mod < 0? mod + cnt_con: mod;
if (lst_nonmatch[mod] >= seg)
return lst_nonmatch[mod];
Loop (i,seg,cnt_seg) {
if (!con2col[(con+i-seg)%cnt_con].count(res[i])) {
lst_nonmatch[mod] = i;
return i;
}
}
lst_nonmatch[mod] = cnt_seg;
return cnt_seg;
}
int minimumInstructions(int cnt_seg, int cnt_con, int cnt_col,
vector<int> res, vector<int> cnt_like,
vector<vector<int>> likes) {
::cnt_seg = cnt_seg;
::cnt_con = cnt_con;
::cnt_col = cnt_col;
Loop (i,0,cnt_seg)
::res[i] = res[i];
Loop (i,0,cnt_con) {
Loop (j,0,cnt_like[i]) {
col2con[likes[i][j]].push_back(i);
con2col[i].insert(likes[i][j]);
}
}
memset(lst_nonmatch, -1, sizeof(lst_nonmatch));
int lst_cover = 0;
Loop (seg,0,cnt_seg-cnt_con+1) {
for (int con : col2con[res[seg]]) {
if (find_nonmatch(seg, con) >= seg + cnt_con) {
lst_cover = seg + cnt_con;
interval_match[seg] = 1;
break;
}
}
if (seg == lst_cover)
return -1;
}
if (!interval_match[cnt_seg-cnt_con])
return -1;
set<int> bag;
lst_cover = 0;
int ans = 0;
Loop (i,0,cnt_seg-cnt_con+1) {
if (interval_match[i])
bag.insert(i + cnt_con);
if (i == lst_cover) {
++ans;
lst_cover = *bag.rbegin();
}
assert(i < lst_cover);
}
if (lst_cover < cnt_seg) {
lst_cover = *bag.rbegin();
++ans;
}
assert(lst_cover == cnt_seg);
return ans;
}
