Submission #414196

#	Time	Username	Problem	Language	Result	Execution time	Memory
414196		prvocislo	Painting Walls (APIO20_paint)	C++17	63 / 100	993 ms	524292 KiB

paint

#include <vector>
using namespace std;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
  vector<vector<int> > f(k); // ktorym kontraktorom sa paci tato farba
  for (int i = 0; i < m; i++) for (int j : b[i]) f[j].push_back(i), f[j].push_back(i + m);
  const int off = n + 5, maxi = 2 * m + n + 10; 
  vector<vector<int> > s(maxi); // ktore indexy maju toto cislo
  for (int i = 0; i < n;i++)
  {
    for (int j : f[c[i]]) s[off + j - i].push_back(i);
  }
  vector<int> st(n, 0); // mozeme na tomto indexe zacat
  for (int i = 0; i < maxi; i++)
  {
    if (s[i].empty()) continue;
    int miss = s[i][0]-1; // posledne ktore nam chyba
    for (int j = 0; j < s[i].size(); j++)
    {
      if (j && s[i][j - 1] != s[i][j] - 1) miss = s[i][j] - 1;
      if (miss + m <= s[i][j])
        st[s[i][j] - (m - 1)] = 1;
    }
  }
  int last = -1; // posledne zafarbene
  int best = -1e9; // najlepsie ktore mozeme zobrat
  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    if (st[i]) best = i;
    if (last < i)
    {
      if (best + m - 1 < i)
       return -1;
      ans ++;
      last = best + m - 1;
    }
  }
  return 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:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int j = 0; j < s[i].size(); j++)
      |                     ~~^~~~~~~~~~~~~

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