Submission #367778

#	Time	Username	Problem	Language	Result	Execution time	Memory
367778		KoD	Painting Walls (APIO20_paint)	C++17	100 / 100	1298 ms	261740 KiB

paint

#ifndef LOCAL
#include "paint.h"
#endif

#include <vector>
#include <iostream>

template <class T>
using Vec = std::vector<T>;

int rem_euclid(int x, const int y) {
    x %= y;
    return x < 0 ? x + y : x;
}

int minimumInstructions(int N, int M, int K, Vec<int> C, Vec<int>, Vec<Vec<int>> B) {
    Vec<Vec<int>> store(K);
    for (int i = 0; i < M; ++i) {
        for (const auto c: B[i]) {
            store[c].push_back(i);
        }
    }
    Vec<Vec<int>> appear(M);
    for (int i = 0; i < N; ++i) {
        for (const auto j: store[C[i]]) {
            appear[rem_euclid(j - i, M)].push_back(i);
        }
    }
    Vec<int> max_right(N);
    for (const auto &vec: appear) {
        int last = N + 1;
        int to_right = 0;
        for (int i = (int) vec.size() - 1; i >= 0; --i) {
            const auto k = vec[i];
            if (k + 1 != last) {
                to_right = 0;
            }
            to_right += 1;
            max_right[k] = std::max(max_right[k], to_right);
            last = k;
        }
    }
    Vec<int> paint;
    for (int i = 0; i < N; ++i) {
        if (max_right[i] >= M) {
            paint.push_back(i);
        }
    }
    int ret = 0;
    int right = 0;
    int idx = 0;
    while (right < N) {
        while (idx < (int) paint.size() && paint[idx] <= right) {
            idx += 1;
        }
        if (idx == 0) {
            return -1;
        }
        const auto left = paint[idx - 1];
        if (left + M <= right) {
            return -1;
        }
        ret += 1;
        right = left + M;
    }
    return ret;
}

#ifdef LOCAL
int main() {
    int N, M, K;
    std::cin >> N >> M >> K;
    Vec<int> C(N);
    Vec<int> A(M);
    Vec<Vec<int>> B(M);
    for (auto &x: C) {
        std::cin >> x;
    }
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i];
        B[i].resize(A[i]);
        for (auto &x: B[i]) {
            std::cin >> x;
        }
    }
    std::cout << minimumInstructions(N, M, K, C, A, B) << '\n';
    return 0;
}
#endif

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