Submission #1273562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273562		mdobric	Boarding Passes (BOI22_passes)	C++20	0 / 100	4 ms	568 KiB

passes

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

const int maxn = 100005, maxg = 20;
int n, g;
string s;
double prosli[maxn][maxg];
int red[maxg];
double ukp[maxg], lijevo[maxn], desno[maxn], dodaj[maxn];
vector <int> mjesta[maxg];
double ans = 1e18;

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++){
		if (i != 0){
			for (int j = 0; j < 15; j++) prosli[i][j] = prosli[i - 1][j];
		}
		int j = s[i] - 'A';
		if (prosli[i][j] == 0) red[g] = j, g++;
		prosli[i][j]++;
		ukp[j]++;
		mjesta[j].push_back(i);
	}
	do{
		double tr = 0;
		for (int i = 0; i < n; i++) lijevo[i] = 0, desno[i] = 0, dodaj[i] = 0;
		for (int i = 0; i < g; i++){
			int x = red[i];
			//cout << x << " red " << endl;
			for (int j = 0; j < mjesta[x].size(); j++){
				int y = mjesta[x][j];
				tr += min(lijevo[y] + (prosli[y][x] - 1) / 2, desno[y] + (ukp[x] - prosli[y][x]) / 2);
				//cout << "tr " << tr << endl;
				//cout << y << " " << prosli[y][x] << " " << ukp[x] << endl;
				//cout << lijevo[y] << " " << desno[y] << endl;
			}
			
			for (int j = 0; j < mjesta[x].size(); j++) dodaj[mjesta[x][j]] = 1;
			for (int j = 0; j < n; j++){
				if (j == 0) lijevo[j] = dodaj[j];
				else lijevo[j] = lijevo[j - 1] + dodaj[j];
			}
			for (int j = n - 1; j >= 0; j--){
				if (j == n - 1) desno[j] = dodaj[j];
				else desno[j] = desno[j + 1] + dodaj[j];
			}
			
		}
		
		//cout << endl;
		ans = min(ans, tr);
		//if (tr == 10.5) cout << red[0] << red[1] << red[2] << red[3] << red[4] << endl;
	}while (next_permutation(red, red + g));
	cout << ans << "\n";	

	return 0;
}

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