Submission #710598

#TimeUsernameProblemLanguageResultExecution timeMemory
710598KoDMonochrome Points (JOI20_monochrome)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> W, B; W.reserve(N); B.reserve(N); for (int i = 0; i < 2 * N; ++i) { char c; cin >> c; (c == 'W' ? W : B).push_back(i); } auto f = [&](int k) { ll ret = 0; for (int i = 0; i < N; ++i) { int j = i + k; if (j >= N) j -= N; int d = abs(W[i] - B[j]); ret += min(d - 1, 2 * N - 1 - d); } return ret / 2; }; int min = -1, max = N; int s = 1, t = 2; while (min + t < max) swap(s += t, t); int a = min, b = min + t, x = min + t - s; ll fx = f(x), fy; while (a + b != 2 * x) { int y = a + b - x; if (y < max and fx < (fy = f(y))) { a = x; x = y; fx = fy; } else { b = a; a = y; } } cout << fx << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...