Submission #1099048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099048		ohad	Boarding Passes (BOI22_passes)	C++14	0 / 100	3 ms	348 KiB

passes

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long double ld;

int main() {
	string a;
	cin >> a;
	int size = a.length();
	vector<bool> chars(26, 0);
	for (auto i : a)
	{
		chars[i - 'A'] = 1;
	}
	vector<int> tosort;
	for (int i = 0; i < 26; i++)
	{
		if (chars[i] == 1)
			tosort.push_back(i);
	}
	sort(tosort.begin(), tosort.end());
	map<int, int> m;
	int counter = 1;
	for (auto i : tosort)
	{
		m[i] = counter;
		counter++;
	}

	vector<int> actual(size, 0);
	for (int i = 0; i < size; i++)
	{
		actual[i] = m[a[i] - 'A'];
	}
	int g = tosort.size();
	vector<int> permutation(g);
	for (int i = 0; i < g; i++)
	{
		permutation[i] = i + 1;
	}
	ld optimal = 1e9;
	do {
		ld t = 0;
		for (int i = 0; i < size; i++)
		{
			ld pas1 = 0;
			ld pas2 = 0;
			for (int j = 0; j < i; j++)
			{
				if (permutation[actual[j]-1] < permutation[actual[i]-1])
					pas1 += 1;
				else if (actual[i] == actual[j])
					pas1 += 0.5;
			}
			for (int j = size; j > i; j--)
			{
				if (permutation[actual[j]-1] < permutation[actual[i]-1])
					pas2 += 1;
				else if (actual[i] == actual[j])
					pas2 += 0.5;
			}
			if (pas2 < pas1)
				swap(pas1, pas2);
			t += pas1;
		}
		if (t+0.00001 < optimal)
			optimal = t;

	} while (next_permutation(permutation.begin(), permutation.end()));
	cout << fixed << setprecision(6) << optimal;
}

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