#include <bits/stdc++.h>
using namespace std;
bool bin_search (vector <int> &V, int val) {
int l = 0, r = int(V.size()) - 1;
while (l <= r) {
int m = (l + r) / 2;
if (V[m] == val) return true;
if (V[m] < val) l = m + 1;
else r = m - 1;
}
return false;
}
bool subtask1 (int N, int M, int pos[], vector <int> &C, int P[]) {
int lft = 0;
if (pos[C[0]] == -1) return 1;
for (int y = 1; y < N; y ++) {
if (pos[C[y]] == -1) return 1;
if (pos[C[y]] != (pos[C[y-1]] + 1) % M) {
for (int i = lft; i <= y - M; i ++) {
P[i] = 1;
}
lft = y;
}
}
for (; lft <= N - M; lft ++)
P[lft] = 1;
return 0;
}
int minimumInstructions (int N, int M, int K, vector <int> C, vector <int> A, vector <vector<int>> B) {
int P[N], L[N], G[N+M], pos[K];
int subtask = 1;
memset(pos, -1, sizeof(pos));
for (int i = 0; i < M; i ++) {
for (int j = 0; j < A[i]; j ++) {
if (pos[B[i][j]] != -1) {
subtask = 0;
}
pos[B[i][j]] = i;
}
}
memset(P, 0, sizeof(P));
if (subtask and subtask1(N, M, pos, C, P)) {
return -1;
}
else {
for (int y = 0; y <= N - M; y ++) {
for (int x = 0; x < M; x ++) {
if (bin_search(B[x], C[y])) {
int flag = 0;
for (int l = 1; l < M; l ++) {
if (!bin_search(B[(x + l) % M], C[y + l])) {
flag = 1;
break;
}
}
if (!flag) {
P[y] = 1;
}
}
}
}
}
if (P[0]) L[0] = 0;
else return -1;
for (int i = 1; i < N; i ++) {
if (P[i]) L[i] = i;
else L[i] = L[i-1];
}
memset(G, 0, sizeof(G));
for (int i = N - 1; i >= 0; i --) {
if (i - L[i] >= M) {
return -1;
}
G[i] = 1 + G[L[i] + M];
}
return G[0];
}
void solve () {
int N, M, K;
vector <int> C, A;
vector <vector<int>> B;
cin >> N >> M >> K;
C.resize(N);
A.resize(M);
B.resize(M);
for (int i = 0; i < N; i ++) {
cin >> C[i];
}
for (int i = 0; i < M; i ++) {
cin >> A[i];
B[i].resize(A[i]);
for (int j = 0; j < A[i]; j ++) {
cin >> B[i][j];
}
}
cout << minimumInstructions(N, M, K, C, A, B) << endl;
}
int main () {
solve();
return 0;
}
Compilation message
/tmp/ccxFSMyR.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccyj1QTg.o:paint.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
