#include "paint.h"
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;
int n, m, K;
vector<int> A, C;
vector<vector<int>> B;
namespace sub1 {
int idxA[N], f[N];
int check () {
rep (i, 0, m - 1) iter (&col, B[i]) f[col]++;
return *max_element (f, f + K) <= 1;
}
int solution() {
rep (i, 0, K - 1) idx[i] = -1;
rep (i, 0, m - 1) {
iter (&col, B[i]) idx[col] = i;
}
int st = idx[C[0]];
if (st == -1) return -1;
int res = 0;
rep (i, 1, n - 1) {
if (i % m == 0) ++res;
(st += 1) %= m;
int pos = lower_bound (B[st], C[i]) - B[st].begin();
if (pos == SZ(B[st]) || B[st][pos] != C[i]) return -1;
}
return res;
}
}
namespace sub4 {
const int N2 = 20000 + 2;
const int M2 = 2000 + 2;
int dp[N2][M2 * 2], f[N];
bool ok[N2];
vector<int> posC[N];
struct Segment_Tree {
int Range;
int st[N << 2];
void init (int n) {
Range = n;
rep (i, 1, n << 2) {
st[i] = INF;
}
}
void update (int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id] = val;
return;
}
int mid = l + r >> 1;
update (id << 1, l, mid, pos, val);
update (id << 1 | 1, mid + 1, r, pos, val);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int get (int id, int l, int r, int u, int v) {
if (l > v || r < u) return INF;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
return min (get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
}
void update (int pos, int val ) {
update (1, 1, Range, pos, val);
}
int get (int u, int v) {
return get (1, 1, Range, u, v);
}
}ST;
int solution() {
A.resize (2 * m);
B.resize (2 * m);
rep (i, m, 2 * m - 1) {
A[i] = A[i - m];
B[i] = B[i - m];
}
rep (i, 0, n - 1) posC[C[i]].push_back(i);
rep (j, 0, 2 * m - 1) {
iter (&col, B[j])
iter (&pos, posC[col]) {
dp[pos][j] = 1;
}
}
reb (i, n - 1, 0) {
reb (j, 2 * m - 1, 0) {
if (dp[i][j] != 0) dp[i][j] = dp[i + 1][j + 1] + 1;
if (dp[i][j] >= m) ok[i + 1] = 1;
}
}
rep (i, 1, n) f[i] = INF;
ST.init(n);
f[m] = ok[1] ? 1 : INF;
ST.update (m, f[m]);
rep (i, 2, n - m + 1) {
if (ok[i]) {
f[i + m - 1] = ST.get (i - 1, i + m - 1) + 1;
ST.update (i + m - 1, f[i + m - 1]);
}
}
if (f[n] < INF) return f[n];
else return -1;
}
}
int minimumInstructions (int _n, int _m, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
//void solution() {
n = _n;
m = _m;
K = _K;
C = _C;
A = _A;
B = _B;
// cin >> n >> m >> K;
// C.resize(n);
// rep (i, 0, n - 1) {
// cin >> C[i];
//
// }
// A.resize (m);
// B.resize (m);
// rep (i, 0, m - 1) {
// cin >> A[i];
// B[i].resize (A[i]);
// rep (j, 0, A[i] - 1) {
// cin >> B[i][j];
// }
// }
if (sub1 :: check())
return sub1 :: solution();
// cout << sub1 :: solution() <<"\n":
else if (n <= 20000 && m <= 2000)
return sub4 :: solution();
// cout << sub4 :: solution() <<"\n";
// else sub5 :: solution();
}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("c");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/
Compilation message
paint.cpp: In function 'int sub1::solution()':
paint.cpp:42:27: error: 'idx' was not declared in this scope; did you mean 'idxA'?
42 | rep (i, 0, K - 1) idx[i] = -1;
| ^~~
| idxA
paint.cpp:44:31: error: 'idx' was not declared in this scope; did you mean 'idxA'?
44 | iter (&col, B[i]) idx[col] = i;
| ^~~
| idxA
paint.cpp:46:18: error: 'idx' was not declared in this scope; did you mean 'idxA'?
46 | int st = idx[C[0]];
| ^~~
| idxA
paint.cpp:52:47: error: no matching function for call to 'lower_bound(__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
52 | int pos = lower_bound (B[st], C[i]) - B[st].begin();
| ^
In file included from /usr/include/c++/10/vector:60,
from paint.h:1,
from paint.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:1350:5: note: candidate: 'template<class _ForwardIterator, class _Tp> _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
1350 | lower_bound(_ForwardIterator __first, _ForwardIterator __last,
| ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_algobase.h:1350:5: note: template argument deduction/substitution failed:
paint.cpp:52:47: note: deduced conflicting types for parameter '_ForwardIterator' ('std::vector<int>' and 'int')
52 | int pos = lower_bound (B[st], C[i]) - B[st].begin();
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from paint.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:2031:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
2031 | lower_bound(_ForwardIterator __first, _ForwardIterator __last,
| ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:2031:5: note: template argument deduction/substitution failed:
paint.cpp:52:47: note: deduced conflicting types for parameter '_FIter' ('std::vector<int>' and 'int')
52 | int pos = lower_bound (B[st], C[i]) - B[st].begin();
| ^
paint.cpp: In member function 'void sub4::Segment_Tree::update(int, int, int, int, int)':
paint.cpp:84:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = l + r >> 1;
| ~~^~~
paint.cpp: In member function 'int sub4::Segment_Tree::get(int, int, int, int, int)':
paint.cpp:92:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = l + r >> 1;
| ~~^~~
paint.cpp: In function 'int main()':
paint.cpp:179:9: error: 'solution' was not declared in this scope
179 | solution();
| ^~~~~~~~
paint.cpp:179:9: note: suggested alternatives:
paint.cpp:41:9: note: 'sub1::solution'
41 | int solution() {
| ^~~~~~~~
paint.cpp:104:9: note: 'sub4::solution'
104 | int solution() {
| ^~~~~~~~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:170:1: warning: control reaches end of non-void function [-Wreturn-type]
170 | }
| ^
