Submission #590306

#	Time	Username	Problem	Language	Result	Execution time	Memory
590306		penguinhacker	Boarding Passes (BOI22_passes)	C++17	100 / 100	105 ms	26600 KiB

passes

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

#define ll long long
#define ar array

const int mxN=1e5, BIT=15;
int n, pref[mxN+1][BIT];
string s;
ll dp[1<<BIT], first[BIT][BIT]; // groups a, b: how many i in group a and j in group b such that i<j
vector<int> oc[BIT], change[BIT][BIT]; // groups a, b: change in taking one more from the front than in the back
vector<ll> change_sum[BIT][BIT];

// we are considering adding group a after b is already all seated

ll C2(int x) {
	return (ll)x*(x-1)/2;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s, n=s.size();
	for (int i=0; i<n; ++i) {
		++pref[i+1][s[i]-'A'];
		oc[s[i]-'A'].push_back(i);
	}
	for (int i=1; i<=n; ++i)
		for (int j=0; j<BIT; ++j)
			pref[i][j]+=pref[i-1][j];
	for (int i=0; i<BIT; ++i)
		for (int j=0; j<BIT; ++j) {
			if (i==j)
				continue;
			for (int k : oc[i])
				first[i][j]+=pref[n][j]-pref[k][j]; // amount of ppl in group j that come after current person
			change[i][j].resize(oc[i].size());
			change_sum[i][j]={0};
			for (int k=0; k<oc[i].size(); ++k) {
				change[i][j][k]=pref[oc[i][k]][j]-(pref[n][j]-pref[oc[i][k]][j]);
				change_sum[i][j].push_back(change_sum[i][j].back()+change[i][j][k]);
			}
		}
	memset(dp, 0x3f, sizeof(dp));
	dp[0]=0;
	for (int mask=0; mask<(1<<BIT); ++mask) {
		for (int i=0; i<BIT; ++i) {
			if (mask&1<<i)
				continue;
			if (oc[i].empty()) {
				dp[mask|1<<i]=min(dp[mask|1<<i], dp[mask]);
				continue;
			}
			int sz=oc[i].size();
			int lb=0, rb=sz;
			while(lb<rb) {
				int mid=(lb+rb+1)/2; // find maximum beneficial change
				int tot_change=mid-1-(sz-mid);
				for (int j=0; j<BIT; ++j)
					if (mask&1<<j)
						tot_change+=2*change[i][j][mid-1];
				if (tot_change<0)
					lb=mid;
				else
					rb=mid-1;
			}
			ll cur=dp[mask]+C2(lb)+C2(sz-lb);
			//if (mask==2)
			//	cout << dp[mask] << " " << lb << " " << cur << " " << first[0][1] << " " << change_sum[0][1][2] << endl;
			for (int j=0; j<BIT; ++j)
				if (mask&1<<j) {
					cur+=2*first[i][j];
					cur+=2*change_sum[i][j][lb];
				}
			dp[mask|1<<i]=min(dp[mask|1<<i], cur);
		}
	}
	ll ans=dp[(1<<BIT)-1];
	cout << ans/2;
	if (ans%2)
		cout << ".5";
	return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int k=0; k<oc[i].size(); ++k) {
      |                  ~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40