oj.uz

Submission #604009

# Submission time Handle Problem Language Result Execution time Memory
604009 2022-07-24T15:14:17 Z MohamedAhmed04 Boarding Passes (BOI22_passes) C++14
0 / 100
 21 ms 468 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 100 + 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 = 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 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
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 11 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 19 ms 324 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 20 ms 212 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

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 11 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 19 ms 324 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 20 ms 212 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -