Submission #1255626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255626		kamrad	Monochrome Points (JOI20_monochrome)	C++20	25 / 100	1213 ms	589824 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroint-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ld  = long double;
using pii = pair<int, int>;
using pint = pair<int, int>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define aint(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 2e3 + 10;

int n;
int oc[maxN];

bool a[maxN];

struct FenTree {
	int bit[maxN];
	void add(int idx) {
		if(idx == 0)
			return;
		for(; idx < maxN; idx += (idx & (-idx)))
			bit[idx]++;
	}
	int get(int idx) {
		int ret = 0;
		for(; idx > 0; idx -= (idx & (-idx)))
			ret += bit[idx];
		return ret;
	}

	void cle() {
		for(int i = 0; i < maxN; i++)
			bit[i] = 0;
	}
} f;

int calc(int l, int r, int k, bool type) {
	int remain = k;
	for(int i = (l+1)%(2*n); i != r%(2*n); i = (i+1)%(2*n)) {
		if(a[i] == type and remain) {
			oc[i] = 1;
			remain--;
		}
	}
	remain = k;
	for(int i = (r-1+2*n)%(2*n); i != l%(2*n); i = (i-1+2*n)%(2*n)) {
		if(a[i] != type and remain) {
			oc[i] = -1;
			remain--;
		}
	}

	int ret = 0;
	int open = 0;
	for(int i = (l+1)%(2*n); i != r%(2*n); i = (i+1)%(2*n)) {
		if(oc[i] == 0)
			ret += open;
		else if(oc[i] == 1)
			ret += open;
		open += oc[i];
	}

	if((r+1)%(2*n) != l) {
		vector <int> Widx;
		vector <int> Bidx;
		int cur = 1;
		for(int i = (r+1)%(2*n); i != l; i = (i+1)%(2*n)) {
			if(a[i])
				Bidx.pb(cur);
			else
				Widx.pb(cur);
			cur++;
		}

		int ptr1 = 0; //on white
		int ptr2 = 0; //on black
		vector <int> val;
		for(int i = (l+1)%(2*n); i != r; i = (i+1)%(2*n)) {
			if(oc[i] == 0) {
				if(a[i]) {
					val.pb(Widx[ptr1]);
					ptr1++;
				}
				else {
					val.pb(Bidx[ptr2]);
					ptr2++;
				}
			}
		}
		
		for(auto x : val) {
			ret += f.get(x-1);
			f.add(x);
		}
		f.cle();
		ret += sz(val);
	}
	for(int i = 0; i < 2*n; i++)
		oc[i] = 0;
	
	return ret;
}

int main() {
	IOS;
	
	cin >> n;
	char c;
	for(int i = 0; i < 2*n; i++) {
		cin >> c;
		a[i] = (c=='B');
	}
	
	int ans = 0;
	int l = 0;
	for(int r = 1; r < 2*n; r++) {
		int W1 = 0;
		int B1 = 0;
		if(a[l] == a[r])
			continue;

		for(int i = (l+1)%(2*n); i != r; i = (i+1)%(2*n)) {
			if(a[i])
				B1++;
			else
				W1++;
		}

		if(2*n-2-B1-W1 > B1+W1) {
			if(n-1-B1 < W1 or n-1-W1 < B1)
				continue;
			int k = n-1-B1-W1;
			maxr(ans, calc(r, l, k, !a[r]));
		}
		else {
			if(W1 < n-1-B1 or B1 < n-1-W1)
				continue;
			int k = W1-(n-1-B1);
			maxr(ans, calc(l, r, k, !a[l]));
		}
	}
	cout << ans;
}

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