oj.uz

Submission #604014

# Submission time Handle Problem Language Result Execution time Memory
604014 2022-07-24T15:18:30 Z MohamedAhmed04 Boarding Passes (BOI22_passes) C++14
30 / 100
 2000 ms 4624 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] , mark[MAX] ;
int n ;

long double pref[MAX] , suff[MAX] ;

string s ;

long double calc(int x)
{
	long double sum = 0 ;
	for(int i = 0 ; i < x ; ++i)
		sum += 0.5 * i ;
	return sum ;
}

vector<int>occ[30] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	n = s.size() ;
	for(int i = 0 ; i < n ; ++i)
		occ[s[i]-'A'].push_back(i) ;
	vector<char>v ;
	for(char c = 'A' ; c <= 'Z' ; ++c)
	{
		if(occ[c-'A'].size())
			v.push_back(c) ;
	}
	long double ans = 1e18 ;
	do
	{
		for(int i = 0 ; i < n ; ++i)
			mark[i] = pref[i] = suff[i] = 0 ;
		long double ex = 0 ;
		for(auto &c : v)
		{
			if(!occ[c-'A'].size())
				continue ;
			long double cnt = 0 , cnt2 = 0 ;
			int last = -1 ;
			for(int i = 0 ; i < n ; ++i)
			{
				cnt += mark[i] ;
				if(s[i] != c)
					continue ;
				pref[i] = cnt + 0.5 * cnt2 ;
				if(last != -1)
					pref[i] += pref[last] ;
				++cnt2 , last = i ;
			}
			cnt = 0 , cnt2 = 0 , last = -1 ;
			for(int i = n-1 ; i >= 0 ; --i)
			{
				cnt += mark[i] ;
				if(s[i] != c)
					continue ;
				suff[i] = cnt + 0.5 * cnt2 ;
				if(last != -1)
					suff[i] += suff[last] ;
				++cnt2 , last = i ;
				mark[i] = 1 ;
			}
			int sz = occ[c-'A'].size() ;
			long double Min = min(pref[occ[c-'A'][sz-1]] , suff[occ[c-'A'][0]]) ;
			for(int i = 0 ; i < sz-1 ; ++i)
				Min = min(Min , pref[occ[c-'A'][i]] + suff[occ[c-'A'][i+1]]) ;
			ex += Min ;
		}
		ans = min(ans , ex) ;
	}while(next_permutation(v.begin() , v.end())) ;
	return cout<<fixed<<setprecision(12)<<ans<<"\n" , 0 ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 4368 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4616 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4624 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 19 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 332 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 6 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 19 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 332 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 5 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 6 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 19 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 16 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 6 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 6 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 5 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 7 ms 332 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 6 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 6 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 5 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 5 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2072 ms 724 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 4368 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4616 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4624 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 19 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 25 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 17 ms 332 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 5 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 6 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 6 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 5 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 6 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 6 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 6 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 5 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 19 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 20 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 16 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 6 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 6 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 5 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 5 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 7 ms 332 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 6 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 6 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 5 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 5 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2072 ms 724 KB Time limit exceeded
47 Halted 0 ms 0 KB -