Submission #708346

#	Time	Username	Problem	Language	Result	Execution time	Memory
708346		Cyanmond	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	339 ms	9408 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]
        for (int i = 0; i < N; ++i) {
            int a = blackPos[i], b = whitePos[i + w];
            while (b >= 2 * N) b -= 2 * N;
        }
        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]);
            }
        }
        int b = 0;
        for (int i = 0; i < N; ++i) {
            if (b == i) ++b;
            while (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;
    };

    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;
}

Compilation message (stderr)

monochrome.cpp: In lambda function:
monochrome.cpp:21:17: warning: unused variable 'a' [-Wunused-variable]
   21 |             int a = blackPos[i], b = whitePos[i + w];
      |                 ^

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