oj.uz

Submission #999729

# Submission time Handle Problem Language Result Execution time Memory
999729 2024-06-16T06:00:24 Z pcc Boarding Passes (BOI22_passes) C++17
100 / 100
 456 ms 169044 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1368 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 1236 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 984 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 11100 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 11100 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 984 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 11100 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 11100 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 8784 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 8796 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 12892 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 13012 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 8924 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 13012 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 13088 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 13008 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 12892 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 12892 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 12892 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 7004 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 2 ms 10956 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 ms 15060 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 16988 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 14940 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 15076 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 5 ms 20308 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 5 ms 18524 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 13 ms 23132 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 10 ms 19420 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 6 ms 11740 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 8 ms 8088 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 9 ms 8240 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 12 ms 8028 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 10 ms 8236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 11 ms 8232 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 10 ms 8244 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 11 ms 8068 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1368 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 1236 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 984 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 11100 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 2 ms 11100 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 8784 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 8796 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 12892 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 13012 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 8924 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 13012 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 13088 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 13008 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 2 ms 12892 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 2 ms 12892 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 2 ms 12892 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 7004 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 2 ms 10956 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 2 ms 15060 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 2 ms 16988 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 2 ms 14940 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 2 ms 15076 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 5 ms 20308 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 5 ms 18524 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 13 ms 23132 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 10 ms 19420 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 6 ms 11740 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 8 ms 8088 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 9 ms 8240 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 12 ms 8028 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 10 ms 8236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 11 ms 8232 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 10 ms 8244 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 11 ms 8068 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 39 ms 1884 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 41 ms 1884 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 728 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 1 ms 1220 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1368 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1236 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 856 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 2 ms 13292 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 2 ms 12888 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 2 ms 12892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 2908 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 2 ms 11100 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 ms 5468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 5 ms 16732 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 11 ms 17500 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 13 ms 10076 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 9 ms 21340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 8 ms 11868 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 9 ms 8028 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 10 ms 8028 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 9 ms 8028 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 10 ms 21340 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 14 ms 17500 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 13 ms 8028 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 454 ms 165960 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 41 ms 3680 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 360 ms 167292 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 153 ms 167276 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 42 ms 11868 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 355 ms 165760 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 444 ms 166736 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 413 ms 168552 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 438 ms 168784 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 402 ms 169044 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 402 ms 169016 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 404 ms 168272 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 243 ms 148124 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 456 ms 169040 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'