Submission #336410

#	Time	Username	Problem	Language	Result	Execution time	Memory
336410		KoD	Virus Experiment (JOI19_virus)	C++17	20 / 100	768 ms	9512 KiB

virus

#include <bits/stdc++.h>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

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

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

constexpr isize dx[] = { 1, 0, -1, 0 };
constexpr isize dy[] = { 0, 1, 0, -1 };
constexpr char dir[] = { 'S', 'E', 'N', 'W' };

int main() {
    usize N, H, W;
    std::cin >> N >> H >> W;
    std::string S;
    std::cin >> S;
    Vec<Vec<usize>> grid(H, Vec<usize>(W));
    for (auto &v: grid) {
        for (auto &x: v) {
            std::cin >> x;
            if (x == 0) {
                x = (usize) -1;
            }
        }
    }
    if (H <= 50 && W <= 50) {
        const auto T = S;
        while (S.size() <= 200000) {
            S += T;
        }
        S += 'X';
        std::array<usize, 16> cont{};
        for (usize set = 0; set < 16; ++set) {
            usize cnt = 0;
            for (const auto c: S) {
                bool ok = false;
                for (usize k = 0; k < 4; ++k) {
                    if (set >> k & 1) {
                        if (dir[k] == c) {
                            ok = true;
                        }
                    }
                }
                if (ok) {
                    cnt += 1;
                } 
                else {
                    cont[set] = std::max(cont[set], cnt);
                    cnt = 0;
                }
            }
        }
        usize ans = H * W + 1, num = 0;
        for (usize sx = 0; sx < H; ++sx) {
            for (usize sy = 0; sy < W; ++sy) {
                if (!(~grid[sx][sy])) {
                    continue;
                }
                Vec<Vec<bool>> used(H, Vec<bool>(W));
                std::queue<std::pair<usize, usize>> que;
                const auto push = [&](const usize i, const usize j) {
                    if (!used[i][j]) {
                        used[i][j] = true;
                        que.emplace(i, j);
                    }
                };
                const auto check = [&](const usize i, const usize j) {
                    if (!(~grid[i][j])) {
                        return false;
                    }
                    usize idx = 0;
                    for (usize k = 0; k < 4; ++k) {
                        const auto ni = (isize) i + dx[k];
                        const auto nj = (isize) j + dy[k];
                        if (ni >= 0 && nj >= 0 && ni < (isize) H && nj < (isize) W) {
                            if (used[ni][nj]) {
                                idx ^= (1 << k);
                            }
                        }
                    }
                    return cont[idx] >= grid[i][j];
                };
                push(sx, sy);
                usize cnt = 0;
                while (!que.empty()) {
                    cnt += 1;
                    const auto [i, j] = que.front();
                    que.pop();
                    for (usize k = 0; k < 4; ++k) {
                        const auto ni = (isize) i + dx[k];
                        const auto nj = (isize) j + dy[k];
                        if (ni >= 0 && nj >= 0 && ni < (isize) H && nj < (isize) W) {
                            if (check(ni, nj)) {
                                push(ni, nj);
                            }
                        }
                    }
                }
                if (ans > cnt) {
                    ans = cnt;
                    num = 0;
                }
                if (ans == cnt) {
                    num += 1;
                }
            }
        }
        std::cout << ans << '\n';
        std::cout << num << '\n';
    }
    else if (std::all_of(S.begin(), S.end(), [&](const char c) { return c == 'W' || c == 'E'; })) {
        const auto T = S;
        while (S.size() <= 200000) {
            S += T;
        }
        S += 'X';
        usize maxW = 0, maxE = 0;
        usize cntW = 0, cntE = 0;
        for (const auto c: S) {
            if (c == 'W') {
                cntW += 1;
            }
            else {
                maxW = std::max(maxW, cntW);
                cntW = 0;
            }
            if (c == 'E') {
                cntE += 1;
            }
            else {
                maxE = std::max(maxE, cntE);
                cntE = 0;
            }
        }
        Vec<Vec<bool>> fromE(H, Vec<bool>(W));
        for (usize i = 0; i < H; ++i) {
            for (usize j = 0; j + 1 < W; ++j) {
                if (maxE >= grid[i][j]) {
                    fromE[i][j] = true;
                }
            }
        }
        Vec<Vec<bool>> fromW(H, Vec<bool>(W));
        for (usize i = 0; i < H; ++i) {
            for (usize j = 1; j < W; ++j) {
                if (maxW >= grid[i][j]) {
                    fromW[i][j] = true;
                }
            }
        }
        usize ans = H * W + 1, num = 0;
        for (usize i = 0; i < H; ++i) {
            Vec<usize> toL(W);
            toL[0] = 1;
            for (usize j = 1; j < W; ++j) {
                toL[j] = (fromE[i][j - 1] ? toL[j - 1] : 0) + 1;
            }
            Vec<usize> toR(W);
            toR[W - 1] = 1;
            for (usize j = W - 1; j --> 0;) {
                toR[j] = (fromW[i][j + 1] ? toR[j + 1] : 0) + 1;
            }
            for (usize j = 0; j < W; ++j) {
                if (!(~grid[i][j])) {
                    continue;
                }
                const auto cnt = toL[j] + toR[j] - 1;
                if (ans > cnt) {
                    ans = cnt;
                    num = 0;
                }
                if (ans == cnt) {
                    num += 1;
                }
            }
        }
        std::cout << ans << '\n';
        std::cout << num << '\n';
    }
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80