#include "paint.h"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>
#include <bits/stdc++.h>
#include <chrono>
#include <random>
// @author: Vlapos
namespace operators
{
template <typename T1, typename T2>
std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
{
in >> x.first >> x.second;
return in;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
{
out << x.first << " " << x.second;
return out;
}
template <typename T1>
std::istream &operator>>(std::istream &in, std::vector<T1> &x)
{
for (auto &i : x)
in >> i;
return in;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
}
// name spaces
using namespace std;
using namespace operators;
// end of name spaces
// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines
// usefull stuff
void boost()
{
ios_base ::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }
const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};
const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
int n = N, m = M, k = K;
vector<vector<int>> col(k);
map<pii, bool> good;
for (int i = 0; i < m; ++i)
for (auto el : B[i])
{
col[el].pb(i);
good[{i, el}];
}
vector<int> isGood(n);
map<int, int> isAdded;
vector<pii> els;
for (int i = 0; i < n; ++i)
{
vector<pii> nels;
int curMaxLen = 0;
for (auto [el, len] : els)
{
if (good.find({(el + 1) % m, C[i]}) != good.end())
{
nels.pb({(el + 1) % m, len + 1});
curMaxLen = max(curMaxLen, len + 1);
}
else
isAdded[el] = 0;
}
swap(nels, els);
for (auto el : col[C[i]])
if (!isAdded[el])
{
isAdded[el] = 1;
els.pb({el, 1});
curMaxLen = max(curMaxLen, 1);
}
if (curMaxLen >= m)
isGood[i - m + 1] = 1;
}
int pr = 0;
int curDone = 0;
int cnt = 0;
while (curDone < n - 1)
{
int curMax = -1;
for (int i = pr; i <= curDone; ++i)
if (isGood[i])
curMax = i;
if (curMax == -1)
break;
cnt++;
pr = curDone + 1;
curDone = curMax + m;
}
if (curDone < n - 1)
return -1;
else
return cnt;
}
// ////////////////////////////
// #include "paint.h"
// #include <cassert>
// #include <cstdio>
// #include <string>
// #include <vector>
// 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;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
