//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
ll add(ll x, ll m) {
x++;
if (x == m) {
x = 0;
}
return x;
}
ll sub(ll x, ll m) {
x--;
if (x == -1) {
x = m - 1;
}
return x;
}
ll minimumInstructions(ll n, ll m, ll k, vector<ll> c, vector<ll> a, vector<vector<ll>> b) {
vector<unordered_set<ll>> all(k);
for (ll i = 0; i < m; i++) {
for (auto j : b[i]) {
all[j].insert(i);
}
}
vector<ll> col(m);
for (ll i = 0; i < n; i++) {
for (auto j : all[c[i]]) {
col[j]++;
}
}
ll sum = col[0] + col.back(), now = 0, lst = m - 1;
for (ll i = 1; i < m; i++) {
if (assign_min(sum, col[i] + col[i - 1])) {
now = i;
lst = i - 1;
}
}
vector<ll> cnow(n, 0), clst(n, 0);
for (ll i = 0; i < n; i++) {
ll nn = i, nx = now;
while (nn < n) {
if (all[c[nn]].find(nx) == all[c[nn]].end()) {
break;
}
cnow[i]++;
nx = add(nx, m);
nn++;
}
nn = i;
nx = now;
while (nn >= 0) {
if (all[c[nn]].find(nx) == all[c[nn]].end()) {
break;
}
clst[i]++;
nx = sub(nx, m);
nn--;
}
}
vector<bool> cand(n, false);
deque<ll> ta, td;
for (ll i = 0; i < n; i++) {
ll sum = cnow[i];
ll st = i;
if (i != 0) {
sum += clst[i - 1];
st -= clst[i - 1];
}
if (sum >= m) {
ta.push_back(st);
td.push_back(st + sum - m);
}
}
ll ns = 0;
sort(ta.begin(), ta.end());
sort(td.begin(), td.end());
for (ll i = 0; i < n; i++) {
while (!ta.empty() && ta.front() == i) {
ns++;
ta.pop_front();
}
cand[i] = ns > 0;
while (!td.empty() && td.front() == i) {
ns--;
td.pop_front();
}
}
lst = 0;
ll can = 0;
ll ans = 0;
while (can < n) {
ll ncan = can;
for (ll j = lst; j <= can; j++) {
if (cand[j]) {
assign_max(ncan, j + m);
}
}
lst = can + 1;
if (ncan == can) {
return -1;
}
ans++;
can = ncan;
}
return ans;
}
#ifdef LOCAL
int main() {
int N, M, K;
assert(3 == scanf("%d %d %d", &N, &M, &K));
std::vector<int> C(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &C[i]));
}
std::vector<int> A(M);
std::vector<std::vector<int>> B(M);
for (int i = 0; i < M; ++i) {
assert(1 == scanf("%d", &A[i]));
B[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j) {
assert(1 == scanf("%d", &B[i][j]));
}
}
int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
printf("%d\n", minimum_instructions);
return 0;
}
#endif
Compilation message
paint.cpp:13:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
13 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
