#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
const int nax = 4e5 + 4;
int n;
int col[nax], dp[nax];
vi perm, ot;
int k = 1;
vi st;
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
int compute(int x)
{
if(x >= n)
return 0 ;
if(dp[x] != -1)
return dp[x];
vpi inter;
int rep = 0;
for(int i= 0 ; i < n; i++)
{
int a = perm[(i + x)%n];
int b = ot[i];
inter.pb({min(a,b), max(a,b)});
}
sort(all(inter));
reverse(all(inter));
FenwickTree fen = FenwickTree(2 * n);
for(int i= 0 ; i < n; i++)
{
int a = inter[i].ff;
int b= inter[i].ss;
rep += fen.sum(a,b);
fen.add(a, 1);
fen.add(b, -1);
}
return dp[x] = rep;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
memset(dp, -1,sizeof(dp));
cin >> n;
k = 1;
while(k < 2 * n)
k = (k << 1);
st.assign(2 * k + 1, 0 );
for(int i = 0 ; i < 2 * n ; i++)
{
char c; cin >> c;
if(c == 'B')
col[i] = 1;
if(col[i])
perm.pb(i);
else
ot.pb(i);
}
int ans = 0 ;
int debut = 0;
int fin = n - 1;
int rep = debut;
while(debut <= fin )
{
int mid = (debut + fin)/2;
//cout << mid << ' ' << compute(mid) << ' ' << compute(mid + 1) << "\n";
if(compute(mid + 1) > compute(mid))
{
rep = mid + 1;
debut = mid + 1;
ans = max(ans, compute(mid + 1));
}
else
{
rep = mid ;
fin = mid - 1;
ans = max(ans, compute(mid ));
}
}
cout << ans;
}
Compilation message
monochrome.cpp: In function 'int32_t main()':
monochrome.cpp:111:13: warning: variable 'rep' set but not used [-Wunused-but-set-variable]
111 | int rep = debut;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
1 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1876 KB |
Output is correct |
20 |
Correct |
1 ms |
1876 KB |
Output is correct |
21 |
Correct |
1 ms |
1876 KB |
Output is correct |
22 |
Correct |
1 ms |
1876 KB |
Output is correct |
23 |
Correct |
1 ms |
1876 KB |
Output is correct |
24 |
Correct |
1 ms |
1876 KB |
Output is correct |
25 |
Correct |
1 ms |
1876 KB |
Output is correct |
26 |
Correct |
1 ms |
1876 KB |
Output is correct |
27 |
Correct |
1 ms |
1876 KB |
Output is correct |
28 |
Correct |
1 ms |
1876 KB |
Output is correct |
29 |
Correct |
2 ms |
1836 KB |
Output is correct |
30 |
Correct |
1 ms |
1876 KB |
Output is correct |
31 |
Correct |
1 ms |
1876 KB |
Output is correct |
32 |
Correct |
1 ms |
1876 KB |
Output is correct |
33 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
1 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1876 KB |
Output is correct |
20 |
Correct |
1 ms |
1876 KB |
Output is correct |
21 |
Correct |
1 ms |
1876 KB |
Output is correct |
22 |
Correct |
1 ms |
1876 KB |
Output is correct |
23 |
Correct |
1 ms |
1876 KB |
Output is correct |
24 |
Correct |
1 ms |
1876 KB |
Output is correct |
25 |
Correct |
1 ms |
1876 KB |
Output is correct |
26 |
Correct |
1 ms |
1876 KB |
Output is correct |
27 |
Correct |
1 ms |
1876 KB |
Output is correct |
28 |
Correct |
1 ms |
1876 KB |
Output is correct |
29 |
Correct |
2 ms |
1836 KB |
Output is correct |
30 |
Correct |
1 ms |
1876 KB |
Output is correct |
31 |
Correct |
1 ms |
1876 KB |
Output is correct |
32 |
Correct |
1 ms |
1876 KB |
Output is correct |
33 |
Correct |
2 ms |
1876 KB |
Output is correct |
34 |
Correct |
5 ms |
2004 KB |
Output is correct |
35 |
Correct |
5 ms |
2008 KB |
Output is correct |
36 |
Correct |
4 ms |
2004 KB |
Output is correct |
37 |
Correct |
4 ms |
2004 KB |
Output is correct |
38 |
Correct |
3 ms |
2004 KB |
Output is correct |
39 |
Correct |
4 ms |
2004 KB |
Output is correct |
40 |
Correct |
3 ms |
2004 KB |
Output is correct |
41 |
Correct |
3 ms |
2004 KB |
Output is correct |
42 |
Correct |
4 ms |
2004 KB |
Output is correct |
43 |
Correct |
4 ms |
2004 KB |
Output is correct |
44 |
Correct |
4 ms |
2004 KB |
Output is correct |
45 |
Correct |
4 ms |
1876 KB |
Output is correct |
46 |
Correct |
4 ms |
2004 KB |
Output is correct |
47 |
Correct |
4 ms |
2004 KB |
Output is correct |
48 |
Correct |
5 ms |
2008 KB |
Output is correct |
49 |
Correct |
3 ms |
1876 KB |
Output is correct |
50 |
Correct |
5 ms |
1876 KB |
Output is correct |
51 |
Correct |
4 ms |
2000 KB |
Output is correct |
52 |
Correct |
5 ms |
2004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
1 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1876 KB |
Output is correct |
20 |
Correct |
1 ms |
1876 KB |
Output is correct |
21 |
Correct |
1 ms |
1876 KB |
Output is correct |
22 |
Correct |
1 ms |
1876 KB |
Output is correct |
23 |
Correct |
1 ms |
1876 KB |
Output is correct |
24 |
Correct |
1 ms |
1876 KB |
Output is correct |
25 |
Correct |
1 ms |
1876 KB |
Output is correct |
26 |
Correct |
1 ms |
1876 KB |
Output is correct |
27 |
Correct |
1 ms |
1876 KB |
Output is correct |
28 |
Correct |
1 ms |
1876 KB |
Output is correct |
29 |
Correct |
2 ms |
1836 KB |
Output is correct |
30 |
Correct |
1 ms |
1876 KB |
Output is correct |
31 |
Correct |
1 ms |
1876 KB |
Output is correct |
32 |
Correct |
1 ms |
1876 KB |
Output is correct |
33 |
Correct |
2 ms |
1876 KB |
Output is correct |
34 |
Correct |
5 ms |
2004 KB |
Output is correct |
35 |
Correct |
5 ms |
2008 KB |
Output is correct |
36 |
Correct |
4 ms |
2004 KB |
Output is correct |
37 |
Correct |
4 ms |
2004 KB |
Output is correct |
38 |
Correct |
3 ms |
2004 KB |
Output is correct |
39 |
Correct |
4 ms |
2004 KB |
Output is correct |
40 |
Correct |
3 ms |
2004 KB |
Output is correct |
41 |
Correct |
3 ms |
2004 KB |
Output is correct |
42 |
Correct |
4 ms |
2004 KB |
Output is correct |
43 |
Correct |
4 ms |
2004 KB |
Output is correct |
44 |
Correct |
4 ms |
2004 KB |
Output is correct |
45 |
Correct |
4 ms |
1876 KB |
Output is correct |
46 |
Correct |
4 ms |
2004 KB |
Output is correct |
47 |
Correct |
4 ms |
2004 KB |
Output is correct |
48 |
Correct |
5 ms |
2008 KB |
Output is correct |
49 |
Correct |
3 ms |
1876 KB |
Output is correct |
50 |
Correct |
5 ms |
1876 KB |
Output is correct |
51 |
Correct |
4 ms |
2000 KB |
Output is correct |
52 |
Correct |
5 ms |
2004 KB |
Output is correct |
53 |
Incorrect |
910 ms |
12752 KB |
Output isn't correct |
54 |
Halted |
0 ms |
0 KB |
- |