#include <bits/stdc++.h>
#define int double
#define lgd double
using namespace std;
lgd dp[(int)(1 << 15) + 42];
vector<int> vals[16];
signed main() {
string s;
cin >> s;
int n = (int)s.size();
/*for (int i = 0; i < n; i++)
s += 'A';*/
int g = 0;
vector<char> comp {};
for (int i = 0; i#include <bits/stdc++.h>
#define int long long
#define lgd long double
using namespace std;
lgd dp[(int)(1 << 15) + 42];
vector<int> vals[16];
signed main() {
string s;
cin >> s;
int n = (int)s.size();
/*for (int i = 0; i < n; i++)
s += 'A';*/
int g = 0;
vector<char> comp {};
for (int i = 0; i < n; i++)
comp.push_back(s[i]);
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
for (int i = 0; i < n; i++)
vals[lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin()].push_back(i);
g = (int)comp.size();
//cout << g << '\n';
dp[0] = 0;
for (int mask = 1; mask < (1 << g); mask++) {
dp[mask] = 1e18;
vector<int> pref (n, 0);
for (int group = 0; group < g; group++)
if (mask & (1 << group))
for (auto& x: vals[group])
pref[x]++;
for (int pos = 1; pos < n; pos++)
pref[pos] += pref[pos - 1];
for (int lst = 0; lst < g; lst++) {
if (mask & (1 << lst)) {
// put everyone to the left
lgd esp = 0;
for (int id = 0; id < (int)vals[lst].size(); id++) {
// inversions bcs of other groups, remove the ones from lst
esp += pref[vals[lst][id]] - (id + 1);
}
// add expected inversions from lst permutations
lgd transi = esp + ((int)vals[lst].size() * ((int)vals[lst].size() - 1)) / 4.;
// fix right limit
for (int id = (int)vals[lst].size() - 1; id >= 0; id--) {
// remove from the left side
esp -= pref[vals[lst][id]];
esp += (id + 1);
// inversions bcs of other groups
esp += pref.back() - pref[vals[lst][id]];
// remove from lst
esp -= (int)vals[lst].size() - (id + 1);
transi = min(transi, esp + (((id) * (id - 1)) + ((int)vals[lst].size() - id) * ((int)vals[lst].size() - (id + 1))) / 4.);
}
dp[mask] = min(dp[mask], dp[mask ^ (1 << lst)] + transi);
}
}
}
cout << fixed << setprecision(42) << (double)dp[(1 << g) - 1] << '\n';
} < n; i++)
comp.push_back(s[i]);
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
for (int i = 0; i < n; i++)
vals[lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin()].push_back(i);
g = (int)comp.size();
//cout << g << '\n';
dp[0] = 0;
for (int mask = 1; mask < (1 << g); mask++) {
dp[mask] = 1e18;
vector<int> pref (n, 0);
for (int group = 0; group < g; group++)
if (mask & (1 << group))
for (auto& x: vals[group])
pref[x]++;
for (int pos = 1; pos < n; pos++)
pref[pos] += pref[pos - 1];
for (int lst = 0; lst < g; lst++) {
if (mask & (1 << lst)) {
// put everyone to the left
lgd esp = 0;
for (int id = 0; id < (int)vals[lst].size(); id++) {
// inversions bcs of other groups, remove the ones from lst
esp += pref[vals[lst][id]] - (id + 1);
}
// add expected inversions from lst permutations
lgd transi = esp + ((int)vals[lst].size() * ((int)vals[lst].size() - 1)) / 4.;
// fix right limit
for (int id = (int)vals[lst].size() - 1; id >= 0; id--) {
// remove from the left side
esp -= pref[vals[lst][id]];
esp += (id + 1);
// inversions bcs of other groups
esp += pref.back() - pref[vals[lst][id]];
// remove from lst
esp -= (int)vals[lst].size() - (id + 1);
transi = min(transi, esp + (((id) * (id - 1)) + ((int)vals[lst].size() - id) * ((int)vals[lst].size() - (id + 1))) / 4.);
}
dp[mask] = min(dp[mask], dp[mask ^ (1 << lst)] + transi);
}
}
}
cout << fixed << setprecision(42) << (double)dp[(1 << g) - 1] << '\n';
}
Compilation message
passes.cpp:18:22: error: stray '#' in program
18 | for (int i = 0; i#include <bits/stdc++.h>
| ^
passes.cpp:19: warning: "int" redefined
19 | #define int long long
|
passes.cpp:2: note: this is the location of the previous definition
2 | #define int double
|
passes.cpp:20: warning: "lgd" redefined
20 | #define lgd long double
|
passes.cpp:3: note: this is the location of the previous definition
3 | #define lgd double
|
passes.cpp:6:23: error: conversion from 'double' to 'long unsigned int' in a converted constant expression
6 | lgd dp[(int)(1 << 15) + 42];
| ~~~~~~~~~~~~~~~^~~~
passes.cpp:6:23: error: could not convert '((double)(1 << 15) + (double)42)' from 'double' to 'long unsigned int'
passes.cpp:6:23: error: size of array 'dp' has non-integral type 'double'
passes.cpp: In function 'int main()':
passes.cpp:18:22: error: expected ';' before 'include'
18 | for (int i = 0; i#include <bits/stdc++.h>
| ^~~~~~~~
| ;
passes.cpp:18:23: error: 'include' was not declared in this scope
18 | for (int i = 0; i#include <bits/stdc++.h>
| ^~~~~~~
passes.cpp:18:32: error: 'bits' was not declared in this scope
18 | for (int i = 0; i#include <bits/stdc++.h>
| ^~~~
passes.cpp:18:37: error: 'stdc' was not declared in this scope; did you mean 'std'?
18 | for (int i = 0; i#include <bits/stdc++.h>
| ^~~~
| std
passes.cpp:21:1: error: expected primary-expression before 'using'
21 | using namespace std;
| ^~~~~
passes.cpp:18:46: error: expected ')' before 'using'
18 | for (int i = 0; i#include <bits/stdc++.h>
| ~ ^
| )
......
21 | using namespace std;
| ~~~~~
passes.cpp:26:15: error: a function-definition is not allowed here before '{' token
26 | signed main() {
| ^
passes.cpp:89:3: error: expected primary-expression before '<' token
89 | } < n; i++)
| ^
passes.cpp:89:8: error: 'i' was not declared in this scope
89 | } < n; i++)
| ^
passes.cpp:102:34: error: invalid operands of types 'int' and 'double' to binary 'operator<<'
102 | for (int mask = 1; mask < (1 << g); mask++) {
| ~ ^~ ~
| | |
| int double
passes.cpp:142:56: error: invalid operands of types 'int' and 'double' to binary 'operator<<'
142 | cout << fixed << setprecision(42) << (double)dp[(1 << g) - 1] << '\n';
| ~ ^~ ~
| | |
| int double
