This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 0;
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 (actual[j] < actual[i])
pas1 += 1;
else if (actual[i] == actual[j])
pas1 += 0.5;
}
for (int j = size; j > i; j--)
{
if (actual[j] < actual[i])
pas2 += 1;
else if (actual[i] == actual[j])
pas2 += 0.5;
}
if (pas2 < pas1)
swap(pas1, pas2);
t += pas1;
}
if (t < optimal)
optimal = t;
} while (next_permutation(permutation.begin(), permutation.end()));
cout << fixed << setprecision(6) << optimal;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |