#include <bits/stdc++.h>
using namespace std;
int prefb[400005], prefw[400005];
vector<int> b, w;
int n;
long long memo[400005];
long long get_ans(int idx) {
if(memo[idx] != -1)
return memo[idx];
idx += 4 * n;
idx %= n;
long long res = 0;
for(int j = 0; j < n; ++j) {
int l = b[j], r = w[(idx + j) % n];
//cout << l << " " << r << endl;
// cari antara l dan r
// kalo misal r < l, maka + 2 * n
if(r < l)
swap(l, r);
// pref[2 * n] - pref[r] + pref[l] buat seg 1
// pref[r] - pref[l] buat seg 2
int b1 = prefb[2 * n] - prefb[r] + prefb[l - 1], w1 = prefw[2 * n] - prefw[r] + prefw[l - 1];
int b2 = prefb[r - 1] - prefb[l], w2 = prefw[r - 1] - prefw[l];
//cout << b1 << " " << b2 << " " << w1 << " " << w2 << endl;
res += min(b1, w2) + min(b2, w1);
}
//cout << idx << " " << res << endl;
return memo[idx] = res;
}
int main() {
cin >> n;
string s;
cin >> s;
for(int i = 0; i < 2 * n; ++i) {
if(s[i] == 'B')
b.push_back(i + 1);
else
w.push_back(i + 1);
}
//cout << "TEST" << endl;
for(int i = 1; i <= 2 * n; ++i) {
prefb[i] = prefb[i - 1];
prefw[i] = prefw[i - 1];
if(binary_search(b.begin(), b.end(), i))
prefb[i]++;
else
prefw[i]++;
}
//cout << "PREF BUILD DONE" << endl;
//cout << b.size() << " " << w.size() << endl;
// try circular ternary search
// try shiftnya banyak
// kalo 2 arah negatif -> binser pisah 2 arah
// kalo 2 arah positif -> answer
// pick arbitrary index then check whether it is 2 arah negatif, 2 arah positif, or 1 arah negatif 1 arah positif
// 2 arah positif -> answer
// 2 arah negatif -> ternary left and right segments
// 1 arah negatif 1 arah positif -> pergi ke arah negatif sampe ketemu index pertama yang positif kanannya
memset(memo, -1, sizeof(memo));
// pick arbitrary index
// cari first positive di kanan dan first positive di kiri
// answer antara cur
// coba get_ans n / 2, n / 2 - 1 dan n / 2 + 1
// assume optimal placement cuma ada 1
// find max antara 0...n - 1
// find last index such that val[i] >= val[0] jika n - 1 ke 0 increasing
// jika decreasing cari smallest index yg val[i] >= val[n - 1]
// nanti dapet rangenya, bs di ternary
int lb, rb;
if(get_ans(0) >= get_ans(n - 1)) {
// find last index where get_ans(i) >= get_ans(0)
int l = 0, r = n - 1, idx;
while(l <= r) {
int mid = (l + r) / 2;
if(get_ans(mid) >= get_ans(0)) {
l = mid + 1;
idx = mid;
}
else {
r = mid - 1;
}
}
lb = 0, rb = idx;
}
else {
// find smallest index where get_ans(i) >= get_ans(n - 1)
int l = 0, r = n - 1, idx;
while(l <= r) {
int mid = (l + r) / 2;
if(get_ans(mid) >= get_ans(n - 1)) {
r = mid - 1, idx = mid;
}
else {
l = mid + 1;
}
}
lb = idx, rb = n - 1;
}
while(lb < rb) {
int m1 = lb + (rb - lb) / 3, m2 = lb + 2 * (rb - lb) / 3;
if(m1 == m2)
++m2;
if(get_ans(m1) >= get_ans(m2))
rb = m2 - 1;
else
lb = m1 + 1;
}
//cout << lb << endl;
cout << get_ans(lb) / 2 << endl;
}
Compilation message
monochrome.cpp: In function 'int main()':
monochrome.cpp:100:27: warning: 'rb' may be used uninitialized in this function [-Wmaybe-uninitialized]
100 | int m1 = lb + (rb - lb) / 3, m2 = lb + 2 * (rb - lb) / 3;
| ~~~~^~~~~
monochrome.cpp:100:38: warning: 'lb' may be used uninitialized in this function [-Wmaybe-uninitialized]
100 | int m1 = lb + (rb - lb) / 3, m2 = lb + 2 * (rb - lb) / 3;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
1 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
1 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
1 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
1 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
2 ms |
3412 KB |
Output is correct |
16 |
Correct |
3 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
2 ms |
3412 KB |
Output is correct |
21 |
Correct |
1 ms |
3412 KB |
Output is correct |
22 |
Correct |
2 ms |
3412 KB |
Output is correct |
23 |
Correct |
2 ms |
3412 KB |
Output is correct |
24 |
Correct |
2 ms |
3412 KB |
Output is correct |
25 |
Correct |
2 ms |
3412 KB |
Output is correct |
26 |
Correct |
2 ms |
3412 KB |
Output is correct |
27 |
Correct |
2 ms |
3412 KB |
Output is correct |
28 |
Correct |
2 ms |
3412 KB |
Output is correct |
29 |
Correct |
3 ms |
3412 KB |
Output is correct |
30 |
Correct |
2 ms |
3412 KB |
Output is correct |
31 |
Correct |
2 ms |
3412 KB |
Output is correct |
32 |
Correct |
2 ms |
3412 KB |
Output is correct |
33 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
1 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
1 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
2 ms |
3412 KB |
Output is correct |
16 |
Correct |
3 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
2 ms |
3412 KB |
Output is correct |
21 |
Correct |
1 ms |
3412 KB |
Output is correct |
22 |
Correct |
2 ms |
3412 KB |
Output is correct |
23 |
Correct |
2 ms |
3412 KB |
Output is correct |
24 |
Correct |
2 ms |
3412 KB |
Output is correct |
25 |
Correct |
2 ms |
3412 KB |
Output is correct |
26 |
Correct |
2 ms |
3412 KB |
Output is correct |
27 |
Correct |
2 ms |
3412 KB |
Output is correct |
28 |
Correct |
2 ms |
3412 KB |
Output is correct |
29 |
Correct |
3 ms |
3412 KB |
Output is correct |
30 |
Correct |
2 ms |
3412 KB |
Output is correct |
31 |
Correct |
2 ms |
3412 KB |
Output is correct |
32 |
Correct |
2 ms |
3412 KB |
Output is correct |
33 |
Correct |
2 ms |
3412 KB |
Output is correct |
34 |
Correct |
3 ms |
3412 KB |
Output is correct |
35 |
Correct |
2 ms |
3412 KB |
Output is correct |
36 |
Correct |
2 ms |
3412 KB |
Output is correct |
37 |
Correct |
2 ms |
3412 KB |
Output is correct |
38 |
Correct |
2 ms |
3412 KB |
Output is correct |
39 |
Correct |
2 ms |
3412 KB |
Output is correct |
40 |
Correct |
3 ms |
3412 KB |
Output is correct |
41 |
Correct |
2 ms |
3412 KB |
Output is correct |
42 |
Correct |
2 ms |
3412 KB |
Output is correct |
43 |
Correct |
2 ms |
3412 KB |
Output is correct |
44 |
Correct |
3 ms |
3412 KB |
Output is correct |
45 |
Correct |
2 ms |
3412 KB |
Output is correct |
46 |
Correct |
2 ms |
3412 KB |
Output is correct |
47 |
Correct |
2 ms |
3412 KB |
Output is correct |
48 |
Correct |
2 ms |
3412 KB |
Output is correct |
49 |
Correct |
4 ms |
3412 KB |
Output is correct |
50 |
Correct |
3 ms |
3540 KB |
Output is correct |
51 |
Correct |
2 ms |
3412 KB |
Output is correct |
52 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
1 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
1 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
2 ms |
3412 KB |
Output is correct |
16 |
Correct |
3 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
2 ms |
3412 KB |
Output is correct |
21 |
Correct |
1 ms |
3412 KB |
Output is correct |
22 |
Correct |
2 ms |
3412 KB |
Output is correct |
23 |
Correct |
2 ms |
3412 KB |
Output is correct |
24 |
Correct |
2 ms |
3412 KB |
Output is correct |
25 |
Correct |
2 ms |
3412 KB |
Output is correct |
26 |
Correct |
2 ms |
3412 KB |
Output is correct |
27 |
Correct |
2 ms |
3412 KB |
Output is correct |
28 |
Correct |
2 ms |
3412 KB |
Output is correct |
29 |
Correct |
3 ms |
3412 KB |
Output is correct |
30 |
Correct |
2 ms |
3412 KB |
Output is correct |
31 |
Correct |
2 ms |
3412 KB |
Output is correct |
32 |
Correct |
2 ms |
3412 KB |
Output is correct |
33 |
Correct |
2 ms |
3412 KB |
Output is correct |
34 |
Correct |
3 ms |
3412 KB |
Output is correct |
35 |
Correct |
2 ms |
3412 KB |
Output is correct |
36 |
Correct |
2 ms |
3412 KB |
Output is correct |
37 |
Correct |
2 ms |
3412 KB |
Output is correct |
38 |
Correct |
2 ms |
3412 KB |
Output is correct |
39 |
Correct |
2 ms |
3412 KB |
Output is correct |
40 |
Correct |
3 ms |
3412 KB |
Output is correct |
41 |
Correct |
2 ms |
3412 KB |
Output is correct |
42 |
Correct |
2 ms |
3412 KB |
Output is correct |
43 |
Correct |
2 ms |
3412 KB |
Output is correct |
44 |
Correct |
3 ms |
3412 KB |
Output is correct |
45 |
Correct |
2 ms |
3412 KB |
Output is correct |
46 |
Correct |
2 ms |
3412 KB |
Output is correct |
47 |
Correct |
2 ms |
3412 KB |
Output is correct |
48 |
Correct |
2 ms |
3412 KB |
Output is correct |
49 |
Correct |
4 ms |
3412 KB |
Output is correct |
50 |
Correct |
3 ms |
3540 KB |
Output is correct |
51 |
Correct |
2 ms |
3412 KB |
Output is correct |
52 |
Correct |
2 ms |
3412 KB |
Output is correct |
53 |
Correct |
101 ms |
8924 KB |
Output is correct |
54 |
Correct |
106 ms |
9368 KB |
Output is correct |
55 |
Correct |
103 ms |
9028 KB |
Output is correct |
56 |
Correct |
102 ms |
9044 KB |
Output is correct |
57 |
Correct |
89 ms |
8944 KB |
Output is correct |
58 |
Correct |
93 ms |
8928 KB |
Output is correct |
59 |
Correct |
91 ms |
8804 KB |
Output is correct |
60 |
Correct |
90 ms |
9088 KB |
Output is correct |
61 |
Correct |
109 ms |
9120 KB |
Output is correct |
62 |
Correct |
95 ms |
9132 KB |
Output is correct |
63 |
Correct |
92 ms |
9052 KB |
Output is correct |
64 |
Correct |
83 ms |
8840 KB |
Output is correct |
65 |
Correct |
91 ms |
8852 KB |
Output is correct |
66 |
Correct |
86 ms |
8876 KB |
Output is correct |
67 |
Correct |
81 ms |
8788 KB |
Output is correct |
68 |
Correct |
76 ms |
8524 KB |
Output is correct |
69 |
Correct |
92 ms |
9132 KB |
Output is correct |
70 |
Correct |
85 ms |
8552 KB |
Output is correct |
71 |
Correct |
45 ms |
9016 KB |
Output is correct |
72 |
Correct |
49 ms |
8932 KB |
Output is correct |
73 |
Correct |
112 ms |
9300 KB |
Output is correct |