Submission #335606

#	Time	Username	Problem	Language	Result	Execution time	Memory
335606		Joshc	Painting Walls (APIO20_paint)	C++11	63 / 100	1539 ms	261940 KiB

paint

#include "paint.h"
#include <vector>
#include <algorithm>
using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int> > B) {
  vector<vector<int> > willing = {}, offer = {}; 
  vector<bool> start = {};
  for (int i=0; i<K; i++) willing.push_back({});
  for (int i=0; i<N; i++) start.push_back(false);
  for (int i=0; i<M; i++) {
    for (int j : B[i]) willing[j].push_back(i);
    offer.push_back({});
  }
  for (int i=0; i<N; i++) {
    for (int j : willing[C[i]]) offer[(j-i%M+M)%M].push_back(i);
  }
  for (vector<int> i : offer) {
    if (i.empty()) continue;
    int l = i[0], r = i[0];
    if (M==1) start[l] = true;
    for (int j=1; j<i.size(); j++) {
      if (r+1==i[j]) {
        r++;
        if (r-l+1>=M)  start[r-M+1] = true;
      } else l = r = i[j];
    }
  }
  vector<int> seg = {};
  for (int i=0; i<N; i++) if (start[i]) seg.push_back(i);
  int l = 0, ans = 0;
  if (seg.empty()) return -1;
  while (true) {
    if (l >= N) return ans;
    if (l > seg.back()+M-1) return -1;
    int s = upper_bound(seg.begin(), seg.end(), l)-seg.begin();
    if (s == 0) return -1;
    s--;
    if (seg[s]+M-1<l) return -1;
    l = seg[s]+M;
    ans++;
  }
}

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:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int j=1; j<i.size(); j++) {
      |                   ~^~~~~~~~~

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