Submission #1176531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176531		JelalTkm	Painting Walls (APIO20_paint)	C++20	100 / 100	174 ms	13708 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

// const int N = 1000 + 10;
// const int md = 1e9 + 7;
// const int INF = 5e6;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
  vector<vector<int>> e(k + 1, vector<int> ());
  for (int i = 0; i < m; i++)
    for (auto j: b[i])
      e[j].push_back(i);
  
  vector<pair<pair<int, int>, pair<int, int>>> p(m + 1);
  for (int i = 0; i <= m; i++) {
    p[i].first = {-1, 0};
    p[i].second = {-1, 0};
  }

  vector<int> v;
  for (int i = n - 1; i >= 0; i--) {
    int mx = 0;
    for (auto j: e[c[i]]) {
      int y = (j + 1) % m;
      p[j].second = p[j].first;
      p[j].first.first = 1; p[j].first.second = i;
      if (p[y].first.second == -1 || p[y].first.second == i + 1) {
        p[j].first.first = p[y].first.first + 1;
      }
      if (p[y].second.second == -1 || p[y].second.second == i + 1) {
        p[j].first.first = max(p[j].first.first, p[y].second.first + 1);
      }
      p[j].first.first = min(p[j].first.first, m);
      mx = max(mx, p[j].first.first);
    }

    if (mx == m)
      v.push_back(i);
  }

  sort(v.begin(), v.end());

  int ans = 0;
  int el = n - 1;
  while (el != -1) {
    int l = lower_bound(v.begin(), v.end(), (el - m + 1)) - v.begin();
    if (l == (int) v.size() || v[l] > el) {
      ans = -1;
      break;
    } else {
      ans++;
      el = v[l] - 1;
    }
  }

  return ans;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     int n, m, k;
//     cin >> n >> m >> k;
//     vector<int> c(n);
//     for (int i = 0; i < n; i++)
//       cin >> c[i];
//     vector<int> a(m);
//     vector<vector<int>> b(m, vector<int> ());
//     for (int i = 0; i < m; i++) {
//       cin >> a[i];
//       for (int j = 0; j < a[i]; j++) {
//         int x;
//         cin >> x;
//         b[i].push_back(x);
//       }
//     }

//     cout << minimumInstructions(n, m, k, c, a, b) << '\n';
//   }

//   return 0;
// }

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