Submission #294180

#	Time	Username	Problem	Language	Result	Execution time	Memory
294180		pit4h	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	465 ms	3724 KiB

monochrome

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
int n;
void inc(int& x) {
	x =  (x+1)%(2*n);	
}
string s;
ll solve(int i) {
	ll ans = 0;
	vector<bool> intersect(2*n, 1);
	int cnt = 1;
	vector<int> matched(2*n, -1);
	matched[0] = matched[i] = 0;
	int b = 1, w = i;			
	inc(w);	
	int iter = 1;
	while(iter<n) {
		while(s[b]!=s[0]) {
			if(matched[b] != -1) {
				intersect[matched[b]] = !intersect[matched[b]];
				if(intersect[matched[b]]) {
					cnt++;
				}
				else {
					cnt--;
				}
			}
			inc(b);
		}

		while(s[w]==s[0]) {
			if(matched[w] != -1) {
				intersect[w] = !intersect[w];
				if(intersect[w]) {
					cnt++;
				}
				else {
					cnt--;
				}
			}
			inc(w);
		}
		matched[b] = matched[w] = b;
		ans += cnt;
		cnt++;
		iter++;
		inc(b); inc(w);
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	cin>>s;
	ll best = 0;
	vector<int> pos;
	for(int i=1; i<2*n; ++i) {
		if(s[i] != s[0]) pos.push_back(i);
	}
	int lo = 0, hi = pos.size()-1;
	while(lo<=hi) {
		int range = (hi-lo)/3;
		ll f1 = solve(pos[lo + range]);
		ll f2 = solve(pos[hi - range]);
		best = max({best, f1, f2});
		if(f1 <= f2) {
			lo = lo + range + 1;
		}
		else {
			hi = hi - range - 1;
		}
	}
	cout<<best;
}

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