#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
const int MAXM = 50004;
vector<ii> D[MAXN];
vector<int> B[MAXM], C[MAXN];
int dp[2 * MAXN], sum[MAXN], *f[MAXN];
int colNeed[MAXN], nArr, mArr, numCol;
bool dx[2003][MAXN], ok[MAXN];
int sub1(void) {
for (int i = 1; i <= nArr; ++i) {
if(sz(C[colNeed[i]]) == 0)
return -1;
dp[i] = C[colNeed[i]][0];
sum[i] = sum[i - 1] + (i > 1 && (dp[i - 1] + 1) % mArr == dp[i]);
}
int res(0), maxi(1), lastok(-mArr);
for (int i = 1; i <= nArr; ++i) {
if(sum[i + mArr - 1] - sum[i] == mArr - 1 && (dp[i + mArr - 1] + 1) % mArr == dp[i])
lastok = i;
if(i == maxi) {
if(lastok + mArr <= i)
return -1;
maxi = lastok + mArr;
++res;
}
}
return res;
}
int sub3(void) {
for (int j = 0; j < mArr; ++j) {
for (int it = 0; it < sz(B[j]); ++it)
dx[j][B[j][it]] = 1;
}
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
ok[i] = 0;
for (int j = 0; j < mArr; ++j) {
ok[i] = 1;
for (int k = 0; k < mArr; ++k)
ok[i] &= (dx[(j + k) % mArr][colNeed[i + k]]);
if(ok[i])
break;
}
}
int res(0), maxi(1), lastok(-mArr);
for (int i = 1; i <= nArr; ++i) {
if(ok[i])
lastok = i;
if(i == maxi) {
if(lastok + mArr <= i)
return -1;
maxi = lastok + mArr;
++res;
}
}
return res;
}
int sub4(void) {
for (int j = 0; j < mArr; ++j) {
for (int it = 0; it < sz(B[j]); ++it)
dx[j][B[j][it]] = 1;
}
for (int i = 0; i <= nArr + 1; ++i) {
f[i] = new int[mArr + 2];
for (int j = 0; j <= mArr + 1; ++j)
f[i][j] = 0;
}
for (int i = nArr; i > 0; --i) {
for (int j = mArr; j > 0; --j)
f[i][j] = f[i + 1][j + 1] + (dx[j - 1][colNeed[i]]);
}
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
for (int j = 0; j < mArr; ++j) {
ok[i] = (f[i][j + 1] + f[i + mArr - j][1] - f[i + mArr][j + 1] == mArr);
if(ok[i])
break;
}
}
int res(0), maxi(1), lastok(-mArr);
for (int i = 1; i <= nArr; ++i) {
if(ok[i])
lastok = i;
if(i == maxi) {
if(lastok + mArr <= i)
return -1;
maxi = lastok + mArr;
++res;
}
}
return res;
}
queue<ii> qu[MAXN];
int magicFunc(void) {
for (int i = 1; i <= nArr; ++i)
sort(C[colNeed[i]].begin(), C[colNeed[i]].end());
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
f[i] = new int[sz(C[colNeed[i]])];
int k(0);
while(k < sz(C[colNeed[i]]) && i - C[colNeed[i]][k] + mArr > nArr)
++k;
if(k < sz(C[colNeed[i]])) {
int id(C[colNeed[i]][k]);
qu[i - id + mArr].push(ii(i, k));
}
for (int it = 0; it < sz(C[colNeed[i]]); ++it)
f[i][it] = 0;
}
for (int i = 0; i <= nArr + mArr; ++i)
dp[i] = 0;
for (int i = nArr; i > 0; --i) {
for (int j = 0; j < sz(C[colNeed[i]]); ++j) {
int id(C[colNeed[i]][j]);
++dp[i - id + mArr];
if(i + mArr - 1 <= nArr)
f[i][it] += dp[i - id + mArr];
}
if(i > mArr) {
for (int it = 0; it < sz(C[colNeed[i - mArr]]); ++it) {
int id(C[colNeed[i - mArr]][it]);
f[i - mArr][it] -= dp[i - id + mArr];
}
}
while(sz(qu[i])) {
int j(qu[i].front().fi), k(qu[i].front().se);
qu[i].pop();
f[j][k] += dp[i + mArr];
if(++k < sz(C[colNeed[j]])) {
int id(C[colNeed[j]][k]);
qu[j - id + mArr].push(ii(j, k));
}
}
}
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
for (int it = 0; it < sz(C[colNeed[i]]); ++it)
ok[i] |= (f[i][it] == mArr);
}
int res(0), maxi(1), lastok(-mArr);
for (int i = 1; i <= nArr; ++i) {
if(ok[i])
lastok = i;
if(i == maxi) {
if(lastok + mArr <= i)
return -1;
maxi = lastok + mArr;
++res;
}
}
return res;
}
int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
nArr = _N, mArr = _M, numCol = _K;
for (int i = 1; i <= nArr; ++i) {
colNeed[i] = _C[i - 1];
C[i].clear();
}
int maxf(0);
for (int i = 0; i < mArr; ++i) {
int szlike(_A[i]);
B[i].clear();
for (int j = 0; j < szlike; ++j) {
B[i].push_back(_B[i][j]);
C[_B[i][j]].push_back(i);
maxf = max(maxf, sz(C[_B[i][j]]));
}
}
/*if(maxf <= 1)
return sub1();
if(nArr <= 500)
return sub3();
if(nArr <= 20000 && mArr <= 2000)
return sub4();*/
return magicFunc();
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "paint"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _A, _C;
vector<vector<int>> _B;
int _N, _M, _K;
cin >> _N >> _M >> _K;
_C.resize(_N);
for (int i = 0; i < _N; ++i) {
cin >> _C[i];
//_C[i] = Random(0, _K - 1); cout << _C[i] << " \n"[i + 1 == _N];
}
vector<int> col; for (int i = 0; i < _K; ++i) col.push_back(i);
_A.resize(_M), _B.resize(_M);
for (int i = 0; i < _M; ++i) {
cin >> _A[i];
//_A[i] = Random(1, _K); cout << _A[i] << ' ';
_B[i].resize(_A[i]);
shuffle(col.begin(), col.end(), rng);
for (int j = 0; j < _A[i]; ++j) {
cin >> _B[i][j];
//_B[i][j] = col[j]; cout << _B[i][j] << " \n"[j + 1 == _A[i]];
}
}
int ans = minimumInstructions(_N, _M, _K, _C, _A, _B);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
Compilation message
paint.cpp: In function 'int magicFunc()':
paint.cpp:161:22: error: 'it' was not declared in this scope; did you mean 'id'?
161 | f[i][it] += dp[i - id + mArr];
| ^~
| id
