Submission #1239447

#TimeUsernameProblemLanguageResultExecution timeMemory
1239447trantrungkeinMonochrome Points (JOI20_monochrome)C++20
0 / 100
3 ms1096 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 6; string s; int n,bi = 0, wi = 0, b[N],w[N],BIT[N]; void update(int id) { for(;id <= 2*n; id += (-id)&id) BIT[id] += 1; } int sum(int id) { int res = 0; for(;id > 0; id -= (-id)&id) res += BIT[id]; return res; } int get(int l, int r) { return (sum(r) - sum(l-1)); } int cal(int k) { vector<pair<int,int>> edge; memset(BIT,0,sizeof(BIT)); for(int i = 0; i < n; i++) { int c = min(w[i],b[(i+k)%n]) , d = max(w[i],b[(i+k)%n]); edge.push_back({c,d}); } sort(edge.begin(),edge.end()); int res = 0; for(auto [l,r] : edge) { res += get(l+1,r+1); update(r+1); } return res; } int max_f(int left, int right) { int N_ITER = 100; for (int i = 0; i < N_ITER; i++) { int x1 = left + (right - left) / 3; int x2 = right - (right - left) / 3; if (cal(x1) > cal(x2)) right = x2; else left = x1; } return cal(left); } int main() { cin >> n >> s; for(int i = 0; i < 2*n; i++) { if(s[i] == 'W') w[wi++] = i; else b[bi++] = i; } cout << max_f(0,2*n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...