제출 #1325183

#제출 시각아이디문제언어결과실행 시간메모리
1325183zwezdinvMonochrome Points (JOI20_monochrome)C++20
100 / 100
43 ms3012 KiB
#include<bits/stdc++.h>


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::vector<int> wh, bl;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'W') wh.push_back(i);
        else bl.push_back(i);
    }
    auto solve = [&](int k) -> long long {
        long long cur = 0;
        for (int i = 0; i < n; ++i) {
            cur += n - std::abs(n - std::abs(bl[(i + k) % n] - wh[i])) - 1;
        }
        return cur;
    };
    int p = 0;
    for (int k = 1 << 20; k; k >>= 1) {
        if (solve(p) < solve((p + k) % n)) p = (p + k) % n;
        if (solve(p) < solve((p - k % n + n) % n)) p = (p - k % n + n) % n;
    }
    std::cout << solve(p) / 2;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...