Submission #717488

#	Time	Username	Problem	Language	Result	Execution time	Memory
717488		schiftyfive4	Painting Walls (APIO20_paint)	C++14	100 / 100	1306 ms	14460 KiB

paint

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

#ifdef LOCAL
#include "../../debug.hpp"
#else
#define debug(...) 42
#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;
  }
  debug(g);
  debug(cnt);
  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]]) {
      int id = ((j - (i - 1)) % M + M) % M;
      debug(i, j, id);
      if (cnt[id] == M) {
        cnt_m--;
      }
      cnt[id]--;
      assert(cnt[j] >= 0);
    }
    debug(cnt);
    for (int j : g[C[i + M - 1]]) {
      int id = (j - (i + M - 1) % M + M) % M;
      cnt[id]++;
      assert(cnt[id] <= M);
      if (cnt[id] == M) {
        cnt_m++;
      }
    }
    debug(cnt);
    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;
  // return (N + M - 1) / M;
}

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:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
paint.cpp:35:3: note: in expansion of macro 'debug'
   35 |   debug(g);
      |   ^~~~~
paint.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
paint.cpp:36:3: note: in expansion of macro 'debug'
   36 |   debug(cnt);
      |   ^~~~~
paint.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
paint.cpp:43:7: note: in expansion of macro 'debug'
   43 |       debug(i, j, id);
      |       ^~~~~
paint.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
paint.cpp:50:5: note: in expansion of macro 'debug'
   50 |     debug(cnt);
      |     ^~~~~
paint.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
paint.cpp:59:5: note: in expansion of macro 'debug'
   59 |     debug(cnt);
      |     ^~~~~

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