Submission #409756

#	Time	Username	Problem	Language	Result	Execution time	Memory
409756		Cyanmond	Painting Walls (APIO20_paint)	C++17	40 / 100	1561 ms	12792 KiB

paint

#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);

  Vec<bool> isok(N - M + 1, false);
  Vec<usize> len(M, 0);

  std::unordered_map<usize, usize> Map;
  for (usize i : range(0, N)) {
    std::unordered_map<usize, usize> New_Map;
    for (const auto idx : tls[C[i]]) {
      setmax(New_Map[idx], Map[(idx + M - 1) % M] + 1);
      if (New_Map[idx] >= M)
        isok[i + 1 - M] = true;
    }
    Map = std::move(New_Map);
  }
  Vec<usize> deq;
  for (usize i : range(0, N - M + 1)) {
    if (isok[i]) {
      if (deq.size() > 1)
        if (i - deq[deq.size() - 2] <= M) deq.pop_back();
      deq.emplace_back(i);
    }
  }

  if ([&]() -> bool {
        if (deq.empty()) return false;
        if (deq[0] != 0) return false;
        if (deq.back() != N - M) return false;
        usize last = 0;
        for (const auto el : deq)
          if (el - last > M)
            return false;
          else
            last = el;
        return true;
      }()) {
    return int(deq.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 (stderr)

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:123:24: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long unsigned int, long unsigned int>::mapped_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |       if (New_Map[idx] >= M)
paint.cpp:132:37: warning: comparison of integer expressions of different signedness: 'usize' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |         if (i - deq[deq.size() - 2] <= M) deq.pop_back();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
paint.cpp: In lambda function:
paint.cpp:140:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long unsigned int>, long unsigned int>::value_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |         if (deq.back() != N - M) return false;
      |             ~~~~~~~~~~~^~~~~~~~
paint.cpp:143:25: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  143 |           if (el - last > M)
      |               ~~~~~~~~~~^~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37