#include <bits/stdc++.h>
using namespace std;
const int inf = 1e7;
int minimumInstructions(int n, int m, int K, vector<int> c, vector<int> a, vector< vector<int> > b) {
vector<bool> can(n);
for (int i = 0; i < n; i++) {
can[i] = false;
}
vector<int> who(K);
for (int i = 0; i < K; i++) who[i] = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < a[i]; j++) {
who[b[i][j]] = i;
}
}
int plus1 = 0;
int other = 0;
for (int i = 0; i < m - 1; i++) {
if (who[c[i]] == -1 || who[c[i + 1]] == -1) {
other++;
} else {
if ((who[c[i + 1]] - who[c[i]] + m) % m == 1) {
plus1++;
} else {
other++;
}
}
}
for (int i = 0; i <= n - m; i++) {
if (other == 0) {
can[i] = true;
}
if (i == n - m) break;
if (who[c[i]] == -1 || who[c[i + 1]] == -1) {
other--;
} else {
if ((who[c[i + 1]] - who[c[i]] + m) % m == 1) {
plus1--;
} else {
other--;
}
}
if (who[c[i + m]] == -1 || who[c[i + m - 1]] == -1) {
other++;
} else {
if ((who[c[i + m]] - who[c[i + m - 1]] + m) % m == 1) {
plus1++;
} else {
other++;
}
}
}
int mx_right[n + 1];
for (int i = 0; i <= n; i++) {
mx_right[i] = -inf;
}
mx_right[0] = 0;
int now_value = 0;
bool OK = true;
for (int i = 0; i < n; i++) {
if (can[i]) {
mx_right[now_value + 1] = i + m;
}
if (i >= mx_right[now_value]) {
now_value++;
if (mx_right[now_value] == -inf) {
OK = false;
break;
}
}
}
if (!OK) {
return -1;
} else {
return now_value;
}
}
/*
int main() {
cout << minimumInstructions(10, 3, 7, {1, 2, 0, 4, 1, 3, 1, 2, 4, 5}, {3, 2, 2}, {{0, 4, 6}, {1, 5}, {2, 3}}) << endl;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |