oj.uz

Submission #604012

# Submission time Handle Problem Language Result Execution time Memory
604012 2022-07-24T15:17:32 Z MohamedAhmed04 Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 3728 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(int i = 'A' ; i < 'A'+7 ; ++i)
		v.push_back(i) ;
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 332 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 328 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 99 ms 364 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2066 ms 3728 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 23 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 24 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 23 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 328 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 15 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 340 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 5 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 5 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 6 ms 328 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 324 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 23 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 24 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 23 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 328 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 15 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 340 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 5 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 5 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 6 ms 328 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 6 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 324 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 11 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 21 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 19 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 328 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 17 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 5 ms 320 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 6 ms 340 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 6 ms 332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 6 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 5 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 5 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 5 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 5 ms 340 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 Incorrect 40 ms 812 KB 1st numbers differ - expected: '12497500.0000000000', found: '0.0000000000', error = '1.0000000000'
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 332 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 328 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 99 ms 364 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2066 ms 3728 KB Time limit exceeded
7 Halted 0 ms 0 KB -