Submission #522504

#	Time	Username	Problem	Language	Result	Execution time	Memory
522504		Cyanmond	Painting Walls (APIO20_paint)	C++17	51 / 100	1020 ms	524292 KiB

paint

#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 5 "library2/utility/lwb.hpp"

template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"

class ReversedRange {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            --itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(std::min(f, l) - 1) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept {
    return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
    return ReversedRange(0, n);
}
#line 7 "paper.cpp"
// #include "paint.h"

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A,
                        std::vector<std::vector<int>> B) {
    auto make_table = [&]() {
        const int s = N - M + 1;

        std::vector<std::vector<int>> likeds(K);
        for (const int i : rep(M)) {
            for (const int j : B[i]) {
                likeds[j].push_back(i);
            }
        }
        std::vector<std::vector<bool>> B2(M, std::vector<bool>(K));
        for (const int i : rep(M)) {
            for (const int j : B[i]) {
                B2[i][j] = true;
            }
        }

        std::vector<bool> ret(s);
        for (const int f : rep(M)) {
            std::vector<int> bads;
            for (const int i : rep(N)) {
                if (not B2[(f + i) % M][C[i]]) {
                    bads.push_back(i);
                }
            }
            bads.push_back(N);
            int last = 0;
            for (const int j : bads) {
                for (const int k : rep(last, j - M + 1)) {
                    ret[k] = true;
                }
                last = j + 1;
            }
        }
        return ret;
    };

    auto calc_answer = [M](std::vector<bool> d) {
        const int s = len(d);
        std::vector<int> r_min(s);
        r_min[s - 1] = d[s - 1] ? s - 1 : s;
        for (const int i : revrep(s - 1)) {
            r_min[i] = d[i] ? i : r_min[i + 1];
        }
        if (r_min[s - 1] == s) {
            return -1;
        }
        int answer = 1, now = s - 1;
        while (now != 0) {
            const int nxt = r_min[std::max(0, now - M)];
            if (nxt == now) {
                return -1;
            }
            ++answer;
            now = nxt;
        }
        return answer;
    };

    const auto table = make_table();
    return calc_answer(table);
}

/*
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);
}
*/

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