Submission #561961

#	Time	Username	Problem	Language	Result	Execution time	Memory
561961		4fecta	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	44 ms	5724 KiB

monochrome

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

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