oj.uz

Submission #717449

# Submission time Handle Problem Language Result Execution time Memory
717449 2023-04-01T23:57:16 Z schiftyfive4 Painting Walls (APIO20_paint) C++14
0 / 100
 0 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -