Submission #565370

#	Time	Username	Problem	Language	Result	Execution time	Memory
565370		Ooops_sorry	Painting Walls (APIO20_paint)	C++14	100 / 100	504 ms	16980 KiB

paint

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

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int INF = 1e9, N = 1000 + 10;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    vector<vector<int>> ind(k);
    set<int> st{-INF};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < a[i]; j++) {
            ind[b[i][j]].pb(i);
        }
    }
    vector<int> mp1(m), mp2(m), arr1(N), arr2(N);
    int ind1 = 0, ind2 = 0;
    for (int i = n - 1; i >= 0; i--) {
        bool good = 0;
        for (auto to : ind[c[i]]) {
            int val = mp1[(to + 1) % m] + 1;
            if (val >= m) {
                good = 1;
            }
            mp2[to] = val;
            arr2[ind2++] = to;
        }
        if (good) st.insert(i);
        while (ind1 > 0) {
            mp1[arr1[--ind1]] = 0;
        }
        swap(mp1, mp2);
        swap(ind1, ind2);
        swap(arr1, arr2);
    }
    int now = 0, cnt = 0;
    while (now < n) {
        auto it = prev(st.upper_bound(now));
        if (*it + m <= now) {
            return -1;
        }
        now = *it + m;
        cnt++;
    }
    return cnt;
}

#ifdef LOCAL

signed main() {
  int N, M, K;
  assert(3 == scanf("%d %d %d", &N, &M, &K));

  vector<int> C(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &C[i]));
  }

  vector<int> A(M);
  vector<vector<int>> B(M);
  for (int i = 0; i < M; ++i) {
    assert(1 == scanf("%d", &A[i]));
    B[i].resize(A[i]);
    for (int j = 0; j < A[i]; ++j) {
      assert(1 == scanf("%d", &B[i][j]));
    }
  }

  int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
  printf("%d\n", minimum_instructions);

  return 0;
}

#endif

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