Submission #534751

#	Time	Username	Problem	Language	Result	Execution time	Memory
534751		RaresFelix	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	60 ms	5352 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, st, dr, mij;
vector<ll> P1, P2;
char C[407171];
ll re(ll k) {
    ll r = 0;
    for(ll i = 0, d; i < n; ++i)
        d = abs(P1[i] - P2[(i + k) % n]), r += min(d, 2 * n - d) - 1;
    return r;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> (C + 1);
    for(ll i = 1; i <= 2 * n; ++i) (C[i] != C[1] ? P2 : P1).push_back(i);
    st = 0, dr = 2 * n - 1;
    while(st < dr) {
        mij = (st + dr + 1) / 2;
        if(re(mij) < re(mij + 1)) st = mij;
        else dr = mij - 1;
    }
    cout << max({re(st), re((st - 1 + 2 * n) % (2 * n)), re((st + 1) % (2 * n))}) / 2 << "\n";
    return 0;
}

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