Submission #732294

#	Time	Username	Problem	Language	Result	Execution time	Memory
732294		Magikarp4000	Painting Walls (APIO20_paint)	C++17	63 / 100	1581 ms	28536 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+1;
int w[MAXN], dp[MAXN];
US<int> col[MAXN];
bool z[MAXN];

int minimumInstructions(
    int n, int m, int K, std::vector<int> c,
    std::vector<int> a, std::vector<std::vector<int>> b) {
  FOR(i,0,m) {
    FOR(j,0,a[i]) col[b[i][j]].insert(i);
  }
  FOR(i,0,m) {
    // cout << i << ": ";
    FORX(u,col[c[i]]) {
      // cout << ((m+u-i)%m) << ' ';
      w[(m+u-i)%m]++;
    }
    // cout << ln;
  }
  vector<int> v;
  FOR(i,0,n) dp[i] = INF;
  dp[0] = 0;
  int cnt = 0;
  FOR(i,0,m) if (w[i] == m) cnt++;
  if (cnt > 0) v.PB(0);
  // cout << ln;
  // cout << 0 << ": ";
  // FOR(j,0,m) cout << w[j] << ' ';
  // cout << ln;
  FOR(i,0,n-m) {
    // cout << i+m << ln;
    FORX(u,col[c[i+m]]) {
      int k = (u-((i)%m)+m)%m;
      int diff = 1-col[c[i]].count(u);
      if (w[k] == m-1 && diff == 1) {
        //cout << "+++++ i: " << i << " u: " << u << ln;
        cnt++;
      }
      w[k] += diff;
    }
    FORX(u,col[c[i]]) {
      int k = (u-((i)%m)+m)%m;
      int diff = col[c[i+m]].count(u)-1;
      if (w[k] == m && diff == -1) {
        //cout << "----- i: " << i << " u: " << u << ln;
        cnt--;
      }
      w[k] += diff;
    }
    if (cnt > 0) v.PB(i+1);
    // cout << i+1 << ": ";
    // FOR(j,0,m) cout << w[j] << ' ';
    // cout << "cnt: " << cnt;
    // cout << ln;
  }
  int vn = v.size();
  if (vn == 0 || v[0] > 0) return -1;
  // cout << ln;
  // FOR(i,0,vn) cout << v[i] << ' ';
  // cout << ln;
  int i = 0, res = 1;
  while (i < vn) {
    int sta = v[i];
    if (i == vn-1) break;
    if (v[i+1] > sta+m) break;
    while (i < vn-1 && v[i+1] <= sta+m) i++;
    res++;
  }
  if (v[i]+m >= n) return res;
  return -1;
}

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