Submission #1201761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201761		aykhn	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) 
{
  vector<int> idx[K];
  for (int i = 0; i < M; i++)
  {
    for (int &j : B[i]) idx[j].push_back(i);
  }
  vector<int> cnt(M, 0);
  int cM = 0;
  vector<int> ok(N, 0);
  for (int i = N - 1; i >= 0; i--)
  {
    for (int &j : idx[C[i]]) 
    {
      cM -= (cnt[(i - j + M) % M]++ == M);
      cM += (cnt[(i - j + M) % M] == M);
    }
    if (i + M < N) for (int &j : idx[C[i + M]]) 
    {
      cM -= (cnt[(i - j + M) % M]-- == M);
      cM += (cnt[(i - j + M) % M] == M);
    }
    if (cM) ok[i] = 1;
  }
  int res = 0;
  for (int l = 0, last = -1, mx = -M; l < N; l++)
  {
    while (last < l)
    {
      last++;
      if (ok[last]) mx = max(mx, last);
    }
    if (mx + M <= l) return -1;
    l = mx + M;
    res++;
  }
  return res;
}

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