Submission #604827

#	Time	Username	Problem	Language	Result	Execution time	Memory
604827		errorgorn	Boarding Passes (BOI22_passes)	C++17	100 / 100	1623 ms	706508 KiB

passes

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int BUF=100005;

struct node{
	int arr[200010]={};
	
	int query(int i,int j){
		i+=BUF,j+=BUF+1;
		
		int res=0;
		while (i<j){
			if (i&1) res+=arr[i++];
			if (j&1) res+=arr[--j];
			i>>=1,j>>=1;
		}
		return res;
	}
};

int n;
string s;
vector<int> pos[15];

node root[15][15][2];

int cnt[15];

int get0(int u,int mask,int l,int r){
	int res=0;
	rep(v,0,15) if (mask&(1<<v)) res+=root[u][v][0].query(l,r);
	return res;
}

int get1(int u,int mask,int l,int r){
	int res=0;
	rep(v,0,15) if (mask&(1<<v)) res+=root[u][v][1].query(l,r);
	return res;
}

int memo[1<<15];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>s;
	n=sz(s);
	
	rep(x,0,n) pos[s[x]-'A'].pub(x);
	
	rep(x,0,n){
		rep(y,0,15) root[s[x]-'A'][y][0].arr[x+BUF]=cnt[y]*(s[x]-'A'==y?1:2);
		cnt[s[x]-'A']++;
	}
	
	memset(cnt,0,sizeof(cnt));
	
	rep(x,n,0){
		rep(y,0,15) root[s[x]-'A'][y][1].arr[x+BUF]=cnt[y]*(s[x]-'A'==y?1:2);
		cnt[s[x]-'A']++;
	}
	
	rep(x,0,15) rep(y,0,15) rep(z,0,2) rep(i,BUF,0){
		root[x][y][z].arr[i]=root[x][y][z].arr[i<<1]+root[x][y][z].arr[i<<1|1];
	}
	
	memset(memo,63,sizeof(memo));
	memo[0]=0;
	
	rep(mask,0,1<<15) rep(bit,0,15) if ((mask&(1<<bit))==0){
		int nm=mask|(1<<bit);
		int lo=-1,hi=sz(pos[bit]),mi;
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			
			if (get0(bit,nm,pos[bit][mi],pos[bit][mi]) < get1(bit,nm,pos[bit][mi],pos[bit][mi])){
				lo=mi;
			}
			else{
				hi=mi;
			}
		}
		
		int res=memo[mask];
		if (0<=lo) res+=get0(bit,nm,0,pos[bit][lo]);
		if (hi<sz(pos[bit])) res+=get1(bit,nm,pos[bit][hi],100004);
		memo[nm]=min(memo[nm],res);
	}
	
	int ans=memo[(1<<15)-1];
	
	cout<<ans/2; if (ans%2) cout<<".5"; cout<<endl;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:97:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |    mi=hi+lo>>1;
      |       ~~^~~

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