Submission #568660

#	Time	Username	Problem	Language	Result	Execution time	Memory
568660		ian2024	Painting Walls (APIO20_paint)	C++14	100 / 100	1034 ms	15080 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

// struct C_HASH {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
//
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM =
// chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x +
// FIXED_RANDOM);
// }
// };
//
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long ll;

const int INF = 1e9 + 5;
const ll INFL = 1e18 + 5;
const int MOD = 1000000007;

#define SIZE(a) (int)(a).size()
#define endl '\n'
#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)

#ifdef LOCAL_PROJECT
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;
}
#else
#define cerr \
  if (false) cerr
#endif

int minimumInstructions(int N, int M, int K, std::vector<int> C,
                        std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<vector<int>> color(K);

  // O(400,000)
  for (int manager = 0; manager < M; ++manager) {
    for (auto u : B[manager]) color[u].push_back(manager);
  }
 
  vector<int> counter(M, 0);
  int valid = 0;
  for (int i = 0; i < M; ++i) {
    for (auto manager : color[C[i]]) {
      counter[(M + i - manager) % M]++;
      if (counter[(M + i - manager) % M] == M) valid++;
    }
  }
  

  vector<ii> intervals;

  if (valid) intervals.push_back({0, M - 1});
  
  for (int i = 1; i < N - M + 1; ++i) {
  	for (auto manager : color[C[i - 1]]) {
      counter[(M + (i - 1) - manager) % M]--;
      if (counter[(M + (i - 1) - manager) % M] == M - 1) valid--;
    }
    
    for (auto manager : color[C[i + M - 1]]) {
      counter[(M + (i + M - 1) - manager) % M]++;
      if (counter[(M + (i + M - 1) - manager) % M] == M) valid++;
    }
    
    if (valid) intervals.push_back({i, i + M - 1});
  }
  
  int curr = -1;
  int cost = 0;
  int ptr = 0;
  int ed = -1;
  for (int i = 0; i <= N - 1; ++i) {
  	if (ptr < intervals.size() and intervals[ptr].first <= i) {
  		ed = max(ed, intervals[ptr].second);
  		ptr++;
  	}
  	
  	if (curr < i) {
  		if (ed < i) return -1;
  		curr = ed;
  		cost++;
  	}
  }
  
  return cost;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:110:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    if (ptr < intervals.size() and intervals[ptr].first <= i) {
      |        ~~~~^~~~~~~~~~~~~~~~~~

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