제출 #550594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550594		hoanghq2004	Painting Walls (APIO20_paint)	C++14	100 / 100	1145 ms	267028 KiB

paint

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define Submit
#ifdef Submit
#include "paint.h"

#endif // Submit

using namespace __gnu_pbds;
using namespace std;

const int N = 1e5 + 10;

vector <int> wh[N], s[N];
int ok[N];

int minimumInstructions(int n, int m, int k, vector <int> C, vector <int> A, vector <vector <int> > B) {
    for (int i = 0; i < m; ++i) {
        for (auto x: B[i])
            wh[x].push_back(i);
    }
    for (int i = 0; i < n; ++i)
        for (auto x: wh[C[i]]) {
            int y = ((x - i) % m + m) % m;
            s[y].push_back(i);
        }
    for (int x = 0; x < m; ++x) {
        int last = -1e9, cnt = 0;
        for (auto i: s[x]) {
            if (i != last + 1) {
                if (cnt >= m) {
                    for (int j = last - cnt + 1; j <= last - m + 1; ++j)
                        ok[j] = 1;
                }
                cnt = 0;
            }
            last = i;
            ++cnt;
        }
        if (cnt >= m) {
            for (int j = last - cnt + 1; j <= last - m + 1; ++j)
                ok[j] = 1;
        }
    }
//    for (int i = 0; i < n; ++i) cout << ok[i] << ' ';
//    cout << '\n';
    int ans = 0;
    if (ok[0] == 0) return -1;
    for (int i = 0; i < n; ++i) ok[i] = (!ok[i] ? ok[i - 1] : i + m);
    for (int L = 0; L < n; ) {
        if (ok[L] <= L) return -1;
        L = ok[L];
        ++ans;
    }
    return ans;
}


#ifndef Submit

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

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

  std::vector<int> A(M);
  std::vector<std::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;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
*/
#endif // Submit

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