제출 #708339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708339		Cyanmond	Monochrome Points (JOI20_monochrome)	C++17	0 / 100	1 ms	304 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;
        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;
        }
        return cnt;
    };

    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: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65