/**
* author: wxhtzdy
* created: 03.07.2022 14:53:44
**/
#include <bits/stdc++.h>
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const int inf = (int) 1e6;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
struct node {
int a = inf; // don't forget to set default value
inline void operator += (node &other) {
a = min(a, other.a);
}
};
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
vector<vector<int>> ids(k);
for (int i = 0; i < m; i++) {
for (int j = 0; j < a[i]; j++) {
ids[b[i][j]].push_back(i);
}
}
vector<int> len(m);
vector<bool> is(n);
for (int i = 0; i < n; i++) {
vector<int> vec;
for (int j : ids[c[i]]) {
vec.push_back(len[(j - 1 + m) % m] + 1);
}
assert(!vec.empty());
if (i > 0) {
for (int j : ids[c[i - 1]]) {
len[j] = 0;
}
}
for (int j = 0; j < (int) vec.size(); j++) {
len[ids[c[i]][j]] = vec[j];
}
is[i] = (*max_element(vec.begin(), vec.end()) >= m);
}
vector<int> dp(n, inf);
fenwick<node> fenw(n);
for (int i = m - 1; i < n; i++) {
if (is[i]) {
if (i == m - 1) {
dp[i] = 1;
} else {
for (int j = i - m + 1; j <= i; j++) {
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
fenw.modify(n - i + 1, {dp[i]});
}
if (dp[n - 1] >= inf) {
return -1;
} else {
return dp[n - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
vector<int> a(m);
vector<vector<int>> b(m);
for (int i = 0; i < m; i++) {
cin >> a[i];
b[i].resize(a[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < a[i]; j++) {
cin >> b[i][j];
}
}
cout << minimumInstructions(n, m, k, c, a, b) << '\n';
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccct2Uus.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cclmmuoo.o:paint.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
