#include <bits/stdc++.h>
#define l long long
using namespace std;
const l LEN = 2005;
l n;
string s;
vector<pair<l, l>> connections;
array<l, LEN> connex;
bool is_in_range(l a, l b, l k) {
if (b >= a) {
return (a <= k && k <= b);
} else {
return (a <= k || b >= k);
}
}
l intersections(l k) {
if (k >= n) return 0;
connections.clear();
l whitecounter = 0;
for (int i = 0; i <= k;) {
whitecounter++;
if (s[whitecounter] != 'B') i++;
}
l sum = 0;
for (int i = 0; i < s.size(); i++) {
while (s[i] == 'W') {
i++;
if (i >= s.size()) break;
}
if (i >= s.size()) break;
connex[i] = whitecounter;
connex[whitecounter] = i;
connections.push_back({i, whitecounter++});
whitecounter %= 2*n;
while (s[whitecounter] == 'B') {
whitecounter++;
whitecounter %= 2*n;
}
}
l cutting = 1;
//start
l white = 0;
//finish
l black = 0;
sum = 0;
pair<l, l> e;
l newwhite, newblack;
for (int i = 0; i < connections.size(); i++) {
e = connections[i];
while (white != e.second) {
newwhite = (white+1)%(n*2);
if (is_in_range(black, white, connex[newwhite])) cutting--;
else cutting++;
white = newwhite;
}
while (black != e.first) {
newblack = black+1;
if (is_in_range(newblack, white, connex[black])) cutting++;
else cutting--;
black = newblack;
}
sum += cutting;
}
return ceil((float)sum/2.0);
}
int main() {
cin >> n >> s;
l c = 0;
while(s[c] != 'B') c++;
s = s.substr(c, s.size()-1) + s.substr(0, c);
l sol = 0;
l t;
for (l i = 1<<20; i > 0; i /= 2) {
//cout << intersections(sol+i) << " " << intersections(sol+i+1) << endl;
t = intersections(sol+i);
if (t < intersections(sol+i+1) && t > 0) {
sol += i;
}
}
cout << intersections(sol+1) << endl;
return 0;
}
Compilation message
monochrome.cpp: In function 'long long int intersections(long long int)':
monochrome.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
monochrome.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if (i >= s.size()) break;
| ~~^~~~~~~~~~~
monochrome.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (i >= s.size()) break;
| ~~^~~~~~~~~~~
monochrome.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < connections.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
