Submission #999729

#	Time	Username	Problem	Language	Result	Execution time	Memory
999729		pcc	Boarding Passes (BOI22_passes)	C++17	100 / 100	456 ms	169044 KiB

passes

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll inf = 1e18;
const int mxg = 15;
const int mxn = 1e5+10;
ll prec[mxg][mxg][mxn];
int G,N;
string s;
vector<int> pos[mxg];
ll dp[1<<mxg];//ans * 4

void getprec(int a,int b){
	if(a == b)return;
	ll sum = 0;
	int cnt = 0;
	for(int i = 0;i<=N;i++){
		if(s[i] == 'A'+a)sum += cnt;
		else if(s[i] == 'A'+b)cnt++;
		prec[a][b][i] += sum;
	}
	sum = 0;
	cnt = 0;
	for(int i = N;i>=0;i--){
		prec[a][b][i] += sum;
		if(s[i] == 'A'+a)sum += cnt;
		else if(s[i] == 'A'+b)cnt++;
	}
	return;
}

ll f(ll from,ll cut,int add){
	ll re = 0;
	for(int i = 0;i<G;i++){
		if(from&(1<<i))re += prec[add][i][cut]*4;
	}
	ll p = upper_bound(pos[add].begin(),pos[add].end(),cut)-pos[add].begin();
	re += p*(p-1)+1ll*(pos[add].size()-p)*(int(pos[add].size())-p-1);
	return re;
}

void trans(int from,int to,int add){
	int l = 0,r = int(pos[add].size());
	for(int i = 0;i<20&&l < r;i++){
		int mid = (l+r)>>1;
		int fl = (mid?f(from,pos[add][mid-1],add):f(from,0,add));
		int fr = f(from,pos[add][mid],add);
		if(fl<=fr)r = mid;
		else l = mid+1;
	}
	//if((from^(1<<add)) == (1<<5)-1)cout<<add<<":"<<l<<' '<<r<<endl;
	if(l)dp[to] = min(dp[to],dp[from]+f(from,pos[add][l-1],add));
	else dp[to] = min(dp[to],dp[from]+f(from,0,add));
	if(r)dp[to] = min(dp[to],dp[from]+f(from,pos[add][r-1],add));
	else dp[to] = min(dp[to],dp[from]+f(from,0,add));
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s;
	N = s.size();
	s = "#"+s;
	for(int i = 1;i<=N;i++){
		pos[s[i]-'A'].push_back(i);
		G = max(G,int(s[i]-'A'+1));
	}
	for(int i = 0;i<G;i++){
		for(int j = 0;j<G;j++){
			getprec(i,j);
		}
	}
	cerr<<"PREC"<<endl;
	fill(dp,dp+(1<<mxg),inf);
	dp[0] = 0;
	for(int i = 0;i<(1<<G);i++){
		for(int j = 0;j<G;j++){
			if(!(i&(1<<j)))trans(i,i^(1<<j),j);
		}
	}
	cerr<<dp[(1<<G)-1]<<'\n';
	cout<<fixed<<setprecision(20)<<double(dp[(1<<G)-1])/4.0<<'\n';
	return 0;
}

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