Submission #1326388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326388		joacru	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	1093 ms	11596 KiB

monochrome

#include <iostream>
#include <algorithm>
#include <vector>

#define forn(i,n) for(int i=0;i<(int)n;++i)

#define DBG(a) cerr<<#a<<" = "<<a<<endl
#define DBGA(a) cerr<<#a<<" = "<<a<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v){
	os<<"[";
	forn(i,SZ(v)){
		if(i) os<<", ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;

const int MAXN = 200005;

int ft[2*MAXN];

void update(int i0, int v){
	for(int i=i0+1;i<2*MAXN;i+=i&-i) ft[i]+=v;
}

int get(int i0){
	int r=0;
	for(int i=i0;i;i-=i&-i) r+=ft[i];
	return r;
}

int get_sum(int i0, int i1){
	return get(i1)-get(i0);
}

vector<int> a;

ll check(int k, vector<int> b){
	int n = SZ(a);
	rotate(b.begin(), b.begin()+k, b.end());
	vector<pair<int,int>> rs;
	forn(i,n){
		int l = a[i], r = b[i];
		if(l > r) swap(l, r);
		rs.push_back({l, r});
		rs.push_back({r, l});
	}
	sort(ALL(rs));
	ll ret = 0;
	for(auto x: rs){
		if(x.first < x.second){
			ret += get_sum(x.first, x.second);
			update(x.second, +1);
		} else{
			update(x.first, -1);
		}
	}
	return ret;
}

void solve(){
	int n;
	string s;
	cin>>n>>s;
		
	#ifdef LOCAL
	a.clear();
	#endif
	
	vector<int> b;
	
	forn(i,2*n){
		if(s[i] == 'W') a.push_back(i);
		else b.push_back(i);
	}
	
	int l=0, r=n+1;
	while(r-l>1){
		int m = (l+r)/2;
		ll x = check(m-1, b), y = check(m, b);
		if(y > x){
			l = m;
		} else{
			r = m; // ???
		}
	}
	
	ll ans = check(l, b);
	cout<<ans<<"\n";
		
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
	freopen("input.in", "r", stdin);
	int tcs;
	cin>>tcs;
	while(tcs--)
	#endif
	solve();
	
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65