#include "bits/stdc++.h"
#ifndef CYN_LOCAL_INCLUDED
#include "paint.h"
#endif
#pragma region header
#define loop(n) for ([[maybe_unused]] size_t lpcnt_ = 0; lpcnt_ < (n); ++lpcnt_)
using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using isize = ptrdiff_t;
using usize = size_t;
template <class T>
using Vec = std::vector<T>;
template <class T, size_t N>
using Arr = std::array<T, N>;
template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;
constexpr i32 infi32 = infty<i32, 2>; // 1073741823
constexpr u32 infu32 = infty<u32, 2>; // 2147483647
constexpr i64 infi64 = infty<i64, 4>; // 2305843009213693951
constexpr u64 infu64 = infty<u64, 4>; // 4611686018427387903
// infi32 / 2 < 10^9
// infi64 / 2 < 2 * 10^18
constexpr char endl = '\n'; // std::endl without flush ('\n')
constexpr usize operator"" _uz(u64 v) { return usize(v); } // size_t literal
inline int popcount(unsigned long long x) noexcept {
#if __cplusplus >= 202002L
return std::popcount(x); // C++20
#else
x = x - ((x >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0x0000007f;
#endif
}
template <class T>
constexpr bool setmin(T& a, const T b) noexcept {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr bool setmax(T& a, const T b) noexcept {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr T difrc(const T a, const T b) noexcept {
return a > b ? a - b : b - a;
}
class range {
using value_type = usize;
struct range_iterator {
value_type itr;
constexpr range_iterator(const value_type pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const range_iterator& other) const noexcept {
return itr != other.itr;
}
constexpr value_type operator*() const noexcept { return itr; }
};
const range_iterator first, last;
public:
constexpr range(const value_type first_, const value_type last_) noexcept
: first(first_), last(last_) {} // [l, r)
constexpr range_iterator begin() const noexcept { return first; }
constexpr range_iterator end() const noexcept { return last; }
};
template <class T>
class span {
using iterator_type = typename std::vector<T>::iterator;
iterator_type first, last;
public:
span(std::vector<T>& v, const usize l, const usize r) noexcept
: first(v.begin() + l), last(v.begin() + r) {} // [l, r)
auto begin() const noexcept { return first; }
auto end() const noexcept { return last; }
};
template <class F>
class rec_lambda {
F f;
public:
explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
template <class... Args>
constexpr auto operator()(Args&&... args) const {
return f(*this, std::forward<Args>(args)...);
}
};
#pragma endregion
int minimumInstructions(int N, int M, int K, Vec<int> C, Vec<int> A,
Vec<Vec<int>> B) {
Vec<Vec<usize>> tls(K); // who like color k ?
for (auto i : range(0, M))
for (auto el : B[i]) tls[el].emplace_back(i);
for (auto& el : tls) std::sort(el.begin(), el.end());
Vec<bool> isok(N - M + 1, false);
Vec<usize> len(M, 0);
Vec<std::pair<usize, usize>> Map(M);
for (usize i : range(0, N)) {
usize ldx = M, tmp = 0;
for (const auto idx : tls[C[i]]) {
usize bef = (idx + M - 1) % M;
auto memo = Map[idx].second;
if (bef == ldx) {
setmax(Map[idx].second, tmp + 1);
} else
setmax(Map[idx].second, Map[bef].second + 1);
if (Map[idx].second >= M) isok[i + 1 - M] = true;
Map[idx].first = i;
ldx = idx;
tmp = memo;
}
}
Vec<usize> que;
for (usize i : range(0, N - M + 1)) {
if (isok[i]) {
if (que.size() > 1)
if (i - que[que.size() - 2] <= M) que.pop_back();
que.emplace_back(i);
}
}
if ([&]() -> bool {
if (que.empty()) return false;
if (que[0] != 0) return false;
if (que.back() != usize(N - M)) return false;
usize last = 0;
for (const auto el : que)
if (el - last > usize(M))
return false;
else
last = el;
return true;
}()) {
return int(que.size());
} else
return -1;
}
#ifdef CYN_LOCAL_INCLUDED
int main() {
int N = 8, M = 3, K = 5;
Vec<int> C = {3, 3, 1, 3, 4, 4, 2, 2};
Vec<int> A = {3, 2, 2};
Vec<Vec<int>> B = {{0, 1, 2}, {2, 3}, {3, 4}};
std::cout << minimumInstructions(N, M, K, C, A, B) << '\n';
}
#endif
Compilation message
paint.cpp:5: warning: ignoring '#pragma region header' [-Wunknown-pragmas]
5 | #pragma region header
|
paint.cpp:107: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
107 | #pragma endregion
|
paint.cpp: In function 'int minimumInstructions(int, int, int, Vec<int>, Vec<int>, Vec<std::vector<int> >)':
paint.cpp:129:27: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
129 | if (Map[idx].second >= M) isok[i + 1 - M] = true;
paint.cpp:139:37: warning: comparison of integer expressions of different signedness: 'usize' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
139 | if (i - que[que.size() - 2] <= M) que.pop_back();
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
