Submission #666506

#TimeUsernameProblemLanguageResultExecution timeMemory
666506mychecksedadBoarding Passes (BOI22_passes)C++17
5 / 100
2 ms1172 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define setp() cout << setprecision(15) #define all(x) x.begin(), x.end() const int N = 1e5 + 100; int n; string s; double dp[N]; vector<int> v[15]; void solve(){ cin >> s; n = s.length(); for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i); if(v[0].size() == n){ double k1 = n/2; double k2 = (n+1)/2; cout << (k1*(k1-1) + (k2)*(k2-1))/4.0; return; } vector<int> p = {0, 1, 2, 3, 4, 5, 6}; double best = -1; do{ double S = 0; vector<bool> vis(n); for(int i = 0; i < 7; ++i){ int a = v[i].size(); double best_k = -1; for(int k = 0; k <= a; ++k){ double sum = 0; int po = 0, cur = 0; for(int j = 0; j <= k; ++j){ while(po != n && po < v[i][j]){ cur += vis[po]; po++; } sum += cur; } po = n - 1; cur = 0; for(int j = a - 1; j > k; --j){ while(po != -1 && po > v[i][j]){ cur += vis[po]; po--; } sum += cur; } for(double i = 2; i <= n; ++i) sum /= i; double k1 = a - k; double val = (k * (k-1) + k1*(k1-1))/4.0 + sum; best_k = (best_k == -1 ? val : min(val, best_k)); } for(int pos: v[i]) vis[pos] = 1; S += best_k; } best = best == -1 ? S : min(best, S); }while(next_permutation(all(p))); cout << best; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int T = 1, aa; // cin >> T;aa=T; setp(); while(T--){ // cout << "Case #" << aa-T << ": "; solve(); } return 0; }

Compilation message (stderr)

passes.cpp: In function 'void solve()':
passes.cpp:17:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if(v[0].size() == n){
      |        ~~~~~~~~~~~~^~~~
passes.cpp: In function 'int main()':
passes.cpp:74:16: warning: unused variable 'aa' [-Wunused-variable]
   74 |     int T = 1, aa;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...