Submission #717449

#	Time	Username	Problem	Language	Result	Execution time	Memory
717449		schiftyfive4	Painting Walls (APIO20_paint)	C++14	0 / 100	0 ms	212 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#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>> g(K);
  for (int i = 0; i < M; i++) {
    for (int j : B[i]) {
      g[j].push_back(i);
    }
  }
  int cnt_m = 0;
  vector<int> cnt(M);
  for (int i = 0; i < M; i++) {
    for (int j : g[C[i]]) {
      int id = (j - i + M) % M;
      cnt[id]++;
      assert(cnt[id] <= M);
      if (cnt[id] == M) {
        cnt_m++;
      }
    }
  }
  if (!cnt_m) {
    return -1;
  }
  int ans = 1;
  int lst = M - 1;
  int best = M - 1;
  for (int i = 1; i + M - 1 < N; i++) {
    for (int j : g[C[i - 1]]) {
      if (cnt[j] == M) {
        cnt_m--;
      }
      cnt[j]--;
    }
    for (int j : g[C[i + M - 1]]) {
      cnt[(j + 1) % M]++;
      assert(cnt[(j + 1) % M] <= M);
      if (cnt[(j + 1) % M] == M) {
        cnt_m++;
      }
    }
    if (cnt_m) {
      best = i + M - 1;
    }
    if (i == lst + 1) {
      if (best < i) {
        return -1;
      }
      ans++;
      lst = best;
    }
  }
  if (best < N - 1) {
    return -1;
  }
  assert(best == N - 1);
  // if (lst < best) {
    // ans++;
  // }
  return ans + 1;
}

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