This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#ifdef DEBUG
#define debug(x...) { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
}
#define light_debug(x) { \
dbg::light = true; \
dbg::dout << __func__ << ":" << __LINE__; \
dbg::dout << " " << #x << " = " << x << endl; \
dbg::light = false; \
}
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
using ll = long long;
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int n; cin >> n;
vector<int> w, b; w.reserve(n), b.reserve(n);
vector<int> w_p(2 * n), b_p(2 * n);
rep(i, n << 1) {
char c; cin >> c;
if(c == 'W') w.push_back(i), w_p[i] = 1;
else b.push_back(i), b_p[i] = 1;
}
partial_sum(all(w_p), w_p.begin());
partial_sum(all(b_p), b_p.begin());
auto w_between = [&](int s, int e) {
int k = (w_p[(e - 1 + 2 * n) % (2 * n)] - w_p[s] + n) % n;
return k;
};
auto b_between = [&](int s, int e) {
int k = (b_p[(e - 1 + 2 * n) % (2 * n)] - b_p[s] + n) % n;
return k;
};
long long ans{};
auto calc = [&](int k) {
k = ((k % n) + n) % n;
static vector<long long> cache(n, -1);
if(~cache[k]) return cache[k];
long long c{};
rep(i, n) {
int j = (i + k) % n;
c += min(w_between(w[i], b[j]), b_between(b[j], w[i]));
}
ckmax(ans, c);
debug(k, c);
return cache[k] = c;
};
auto check = [&](int i) {
return calc(i) - calc(i - 1) > 0;
};
if(n <= 5) { // Edge cases.
rep(i, n) calc(i);
cout << ans << '\n';
return 0;
}
int t{-1};
if(check(0)) {
if(check(n - 1)) {
int p{n >> 1};
while(check(p)) ++p;
p %= n;
t = 0;
for(int k{1 << __lg(p)}; k > 0; k >>= 1)
if(t + k < p && check(t + k))
t += k;
} else {
t = 0;
for(int k{1 << __lg(n)}; k > 0; k >>= 1)
if(t + k < n && check(t + k))
t += k;
}
} else {
if(check(n - 1))
t = n - 1;
else {
int p{n >> 1};
while(!check(p)) ++p;
p %= n;
t = p;
for(int k{1 << __lg(n - p)}; k > 0; k >>= 1)
if(t + k < n && check(t + k))
t += k;
}
}
debug(t);
assert(check(t) && !check(t + 1));
cout << ans << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl;
#endif
return 0;
}
Compilation message (stderr)
monochrome.cpp: In lambda function:
monochrome.cpp:33:29: warning: statement has no effect [-Wunused-value]
33 | #define debug(x...) 42
| ^~
monochrome.cpp:88:9: note: in expansion of macro 'debug'
88 | debug(k, c);
| ^~~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:33:29: warning: statement has no effect [-Wunused-value]
33 | #define debug(x...) 42
| ^~
monochrome.cpp:133:5: note: in expansion of macro 'debug'
133 | debug(t);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |