Submission #1217819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217819		MuhammadSaram	Boarding Passes (BOI22_passes)	C++20	100 / 100	336 ms	366012 KiB

passes

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) v.begin(), v.end()

const int M = 100000, N = 15;

int pre[N][M],pre1[N][N][M],pre2[N][N][M],dp[1<<N],sz[N];
vector<int> a[N];

int get(int p,vector<int> v)
{
	int ans=0;
	for (int i:v)
		ans+=pre[i][p];
	return ans*2;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	cout<<fixed<<setprecision(10);
	
	string s;
	cin>>s;
	int n=s.size();
	for (int i=0;i<n;i++)
		a[s[i]-'A'].push_back(i);
	for (int i=0;i<N;i++)
	{
		sz[i]=a[i].size();
		for (int j:a[i])
			pre[i][j]++;
		for (int j=1;j<M;j++)
			pre[i][j]+=pre[i][j-1];
	}
	for (int i=0;i<N;i++)
		for (int j=0;j<N;j++)
		{
			for (int k:a[i])
				pre1[i][j][k]=(k?pre[j][k-1]:0),
				pre2[i][j][k]=pre[j][M-1]-pre[j][k];
			for (int k=1;k<M;k++)
				pre1[i][j][k]+=pre1[i][j][k-1];
			for (int k=M-2;k>=0;k--)
				pre2[i][j][k]+=pre2[i][j][k+1];
		}
	int fin=0;
	for (int m=1;m<(1<<N);m++)
	{
		if (__builtin_popcount(m)==1)
		{
			int p=31-__builtin_clz(m);
			if (sz[p]) fin+=m;
			else continue;
			dp[m]=(sz[p]/2)*(sz[p]/2-1)/2+(sz[p]-sz[p]/2)*(sz[p]-sz[p]/2-1)/2;
			continue;
		}
		dp[m]=n*(n-1)/2;
		vector<int> v;
		int su=0;
		for (int p=0;p<N;p++)
			if (m>>p&1 && sz[p]) v.push_back(p),su+=pre[p][M-1]*2;
		for (int i:v)
		{
			su-=pre[i][M-1];
			int s=-1,e=sz[i];
			while (s+1<e)
			{
				int mid=(s+e)/2;
				int p=get(a[i][mid],v)-pre[i][a[i][mid]];
				if (p*2-1-su<=0)
					s=mid;
				else
					e=mid;
			}
			int x=0;
			for (int j:v)
			{
				int mu=1+(i!=j);
				if (s>=0) x+=pre1[i][j][a[i][s]]*mu;
				if (s+1<sz[i]) x+=pre2[i][j][a[i][s+1]]*mu;
			}
			dp[m]=min(dp[m],dp[m^(1<<i)]+x);
			su+=pre[i][M-1];
		}
	}
	// cout<<dp[3]<<endl;
	if (dp[fin]%2) s=".5";
	else s="";
	cout<<dp[fin]/2<<s<<endl;
	
	return 0;
}

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