Submission #492304

#	Time	Username	Problem	Language	Result	Execution time	Memory
492304		alextodoran	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2084 ms	4804 KiB

monochrome

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N;

string s;

vector <int> v[2];

bool intersect (int a1, int a2, int b1, int b2) {
    if (a1 > a2) {
        swap(a1, a2);
    }
    if (b1 > b2) {
        swap(b1, b2);
    }
    if (a1 < b1 && b1 < a2 && a2 < b2) {
        return true;
    }
    if (b1 < a1 && a1 < b2 && b2 < a2) {
        return true;
    }
    return false;
}

int solve (int offs) {
    vector <pair <int, int>> segments;
    for (int i = 0; i < N; i++) {
        int j = (i + offs) % N;
        segments.push_back(make_pair(v[0][i], v[1][j]));
    }
    int cnt = 0;
    for (int i = 0; i < (int) segments.size(); i++) {
        for (int j = i + 1; j < (int) segments.size(); j++) {
            cnt += intersect(segments[i].first, segments[i].second,
                             segments[j].first, segments[j].second);
        }
    }
    return cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> s;

    for (int i = 0; i < N * 2; i++) {
        v[(s[i] == 'B')].push_back(i);
    }

    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (solve(mid) < solve(mid + 1)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    cout << solve(l) << "\n";

    return 0;
}

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