oj.uz

Submission #1099045

# Submission time Handle Problem Language Result Execution time Memory
1099045 2024-10-10T12:49:02 Z ohad Boarding Passes (BOI22_passes) C++14
0 / 100
 2000 ms 860 KB 
#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]] < permutation[actual[i]])
					pas1 += 1;
				else if (actual[i] == actual[j])
					pas1 += 0.5;
			}
			for (int j = size; j > i; j--)
			{
				if (permutation[actual[j]] < permutation[actual[i]])
					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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2098 ms 860 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 1st numbers differ - expected: '1.0000000000', found: '3.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 1st numbers differ - expected: '1.0000000000', found: '3.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2098 ms 860 KB Time limit exceeded
7 Halted 0 ms 0 KB -