Submission #534749

#	Time	Username	Problem	Language	Result	Execution time	Memory
534749		RaresFelix	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	45 ms	3400 KiB

monochrome

#include <bits/stdc++.h>
#define MN 407171

using namespace std;
int n;
vector<int> P1, P2;
char C[MN];
using ll = long long;

ll re(int k) {
    ll r = 0;
    for(int i = 0; i < n; ++i) {
        int p1 = P1[i], p2 = P2[(i + k) % n];
        r += min(abs(p1 - p2) - 1, 2 * n - (abs(p1 - p2) + 1));
    }
    return r;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> (C + 1);
    int bp = -1, ndif = INT_MAX;
    for(int i = 1; i <= 2 * n; ++i)
        (C[i] != C[1] ? P2 : P1).push_back(i);
    int st = 0, dr = 2 * n - 1, mij;
    while(st < dr) {
        mij = (st + dr + 1) >> 1;
        if(re(mij) < re(mij + 1)) st = mij;
        else dr = mij - 1;
    }
    ll rez = max({re(st), re((st - 1 + 2 * n) % (2 * n)), re((st + 1) % (2 * n))});
    cout << rez / 2 << "\n";
    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:23:9: warning: unused variable 'bp' [-Wunused-variable]
   23 |     int bp = -1, ndif = INT_MAX;
      |         ^~
monochrome.cpp:23:18: warning: unused variable 'ndif' [-Wunused-variable]
   23 |     int bp = -1, ndif = INT_MAX;
      |                  ^~~~

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