Submission #973037

#TimeUsernameProblemLanguageResultExecution timeMemory
973037idasBoarding Passes (BOI22_passes)C++11
0 / 100
6 ms708 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr) #define FOR(i, begin, end) for(int i=(begin); i<(end); i++) #define sz(x) int((x).size()) #define pb push_back #define s second #define f first using namespace std; typedef vector<int> vi; typedef pair<int, int> pii; typedef tuple<int, int, int> tiii; typedef long double ld; typedef long long ll; const int INF=1e9; const int N=1e5+10; int n; string s; int main() { FAST_IO; cin >> s; n=sz(s); set<char> dif; FOR(i, 0, n) { dif.insert(s[i]); } int m=sz(dif); vector<char> ar(dif.begin(), dif.end()); ld ans=-1; do{ FOR(i, -1, n) { ld now=0; set<char> v; FOR(k, 0, m) { int row=0, add=0; FOR(j, 0, n) { if(j>i) break; if(v.count(s[j])) add++; else if(s[j]==ar[k]){ now+=add; row++; now+=row*(row-1)/ld(4); } } row=0; add=0; for(int j=n-1; j>=0; j--){ if(j<=i) break; if(v.count(s[j])) add++; else if(s[j]==ar[k]){ now+=add; row++; now+=row*(row-1)/ld(4); } } v.insert(ar[k]); } if(ans==-1) ans=now; else ans=min(ans, now); // cout << now << endl; } } while(next_permutation(ar.begin(), ar.end())); cout << fixed << setprecision(4) << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...