Submission #708339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708339	2023-03-11T15:24:42 Z	Cyanmond	Monochrome Points (JOI20_monochrome)	C++17	0 / 100	1 ms	304 KB

monochrome

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;
    std::vector<int> blackPos, whitePos;
    for (int i = 0; i < 2 * N; ++i) {
        if (S[i] == 'B') blackPos.push_back(i);
        if (S[i] == 'W') whitePos.push_back(i);
    }
    for (int i = 0; i < 3 * N; ++i) blackPos.push_back(blackPos[i] + 2 * N);
    for (int i = 0; i < 3 * N; ++i) whitePos.push_back(whitePos[i] + 2 * N);

    auto calc = [&](const int w) {
        // blackPos[i] - whitePos[i + w]
        std::vector<std::pair<int, int>> ps;
        for (int i = 0; i < N; ++i) {
            int a = blackPos[i], b = whitePos[i + w];
            while (b >= 2 * N) b -= 2 * N;
            ps.push_back({a, b});
        }
        i64 cnt = 0;
        for (int i = 0; i < N; ++i) {
            int b = i + 1;
            while (b != i and blackPos[b] < whitePos[i + w] and whitePos[b + w] < blackPos[i] + 2 * N) {
                ++b;
            }
            cnt += b - i - 1;
        }
        return cnt;
    };

    int l = -1, r = N;
    while (r - l > 2) {
        int x1 = (2 * l + r) / 3, x2 = (l + 2 * r) / 3;
        const auto v1 = calc(x1), v2 = calc(x2);
        if (v1 > v2) r = x2;
        else l = x1;
    }
    std::cout << calc((l + r) / 2) << std::endl;
}

Subtask #1

0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Incorrect	0 ms	212 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Incorrect	0 ms	212 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Incorrect	0 ms	212 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Incorrect	0 ms	212 KB	Output isn't correct
13	Halted	0 ms	0 KB	-