Submission #708343

#	Time	Username	Problem	Language	Result	Execution time	Memory
708343		Cyanmond	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2035 ms	460 KiB

monochrome

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;
    std::vector<int> blackPos, whitePos;
    for (int i = 0; i < 2 * N; ++i) {
        if (S[i] == 'B') blackPos.push_back(i);
        if (S[i] == 'W') whitePos.push_back(i);
    }
    for (int i = 0; i < 3 * N; ++i) blackPos.push_back(blackPos[i] + 2 * N);
    for (int i = 0; i < 3 * N; ++i) whitePos.push_back(whitePos[i] + 2 * N);

    auto calc = [&](const int w) {
        // blackPos[i] - whitePos[i + w]
        std::vector<std::pair<int, int>> ps;
        for (int i = 0; i < N; ++i) {
            int a = blackPos[i], b = whitePos[i + w];
            while (b >= 2 * N) b -= 2 * N;
            ps.push_back({a, b});
        }
        i64 cnt = 0;
        std::vector<int> ids;
        for (int i = 0; i < N; ++i) {
            if (blackPos[i] > whitePos[i + w]) {
                ids.push_back(i);
                std::swap(blackPos[i], whitePos[i + w]);
                std::swap(blackPos[i + N], whitePos[i + N + w]);
                std::swap(blackPos[i + 2 * N], whitePos[i + 2 * N + w]);
            }
        }
        for (int i = 0; i < N; ++i) {
            int b = i + 1;
            while (b != i and blackPos[b] < whitePos[i + w] and whitePos[b + w] < blackPos[i] + 2 * N) {
                ++b;
            }
            cnt += b - i - 1;
        }
        for (const int i : ids) {
            std::swap(blackPos[i], whitePos[i + w]);
            std::swap(blackPos[i + N], whitePos[i + N + w]);
            std::swap(blackPos[i + 2 * N], whitePos[i + 2 * N + w]);
        }
        return cnt;
    };

    i64 answer = 0;
    for (int i = 0; i < N; ++i) answer = std::max(answer, calc(i));
    std::cout << answer << std::endl;
    return 0;

    int l = -1, r = N;
    while (r - l > 2) {
        int x1 = (2 * l + r) / 3, x2 = (l + 2 * r) / 3;
        const auto v1 = calc(x1), v2 = calc(x2);
        if (v1 > v2) r = x2;
        else l = x1;
    }
    std::cout << calc((l + r) / 2) << std::endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65