제출 #561961

#제출 시각아이디문제언어결과실행 시간메모리
5619614fectaMonochrome Points (JOI20_monochrome)C++17
100 / 100
44 ms5724 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 400005;

int n;
string s;
vector<int> a, b;

int calc(int x) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        int l = a[i], r = b[(i + x) % n];
        if (l > r) swap(l, r);
        int p1 = r - l - 1, p2 = 2 * n - p1 - 2;
        ret += min(p1, p2);
    }
    return ret / 2;
}

int32_t main() {
    boost();

    cin >> n >> s;
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == 'B') a.push_back(i);
        else b.push_back(i);
    }
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (calc(mid) < calc(mid + 1)) lo = mid + 1;
        else hi = mid;
    }
    printf("%lld\n", calc(lo));

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...