Submission #1028165

#TimeUsernameProblemLanguageResultExecution timeMemory
1028165anangoBoarding Passes (BOI22_passes)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<62; void solve() { string S; cin >> S; int n = S.size(); vector<int> ar(n); for (int i=0; i<n; i++) ar[i] = (S[i]-'A'); int G = *max_element(ar.begin(), ar.end()); G++; int pref[n+1][G]; //count of character c, before index i int suff[n+1][G]; //count of character c, after or equal to index i for (int i=0; i<=n; i++) { for (int j=0; j<G; j++) { pref[i][j] = suff[i][j] = 0; } } for (int i=0; i<n; i++) { for (int j=0; j<=G; j++) { if (j==ar[i]) { pref[i+1][j] = pref[i][j]+1; } else { pref[i+1][j] = pref[i][j]; } } } for (int i=n-1; i>=0; i--) { for (int j=0; j<G; j++) { if (j==ar[i]) { suff[i][j] = suff[i+1][j]+1; } else { suff[i][j] = suff[i+1][j]; } } } //everyone before L boards from the front, everyone after or equal to it boards from the back. vector<vector<int>> counts(G,vector<int>(G,0)); //counts[i][j] = sum of subsequences of (i,j) before l, and subsequences of (j,i) after L //counts[i][j] = sum of pref[k][j] for k<=L and ar[k]=i, and analogous expression for the suffix //first, get initial count values (for everyone boarding from the back) for (int j=0; j<G; j++) { for (int k=0; k<n; k++) { int i = ar[k]; //cout << "adding " << i <<" " << j <<" " << k <<" " << j << " " << suff[k][j] << endl; counts[i][j] += suff[k+1][j]; } } /*for (int i=0; i<G; i++) { for (int j=0; j<G; j++) { cout << i <<" " << j <<" " << counts[i][j] << endl; } }*/ int ans = 1LL<<62; vector<int> dp; for (int L=0; L<n; L++) { //counts[i][j] = number of swaps required if i goes after j dp=vector<int>(1<<G,INF); //dp[mask] = min cost if this mask is at the beginning of the ordering dp[0] = 0; for (int mask=0; mask<1<<G; mask++) { for (int addon=0; addon<G; addon++) { if (mask&(1<<addon)) continue; int al = 0; for (int j=0; j<G; j++) { if (mask&(1<<j)) { al+=counts[addon][j]; } } //cout << mask <<" " << addon <<" " << al <<endl; dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+al); } } int self=0; for (int i=0; i<G; i++) { self+=counts[i][i]; } ans=min(ans,2*dp[(1<<G)-1]+self); //transfer L to the right int cur = ar[L]; for (int j=0; j<G; j++) { int delta = suff[L+1][j]; int delta2 = pref[L][j]; counts[cur][j] -= delta-delta2; } /*cout << "TRANSFERRED TO " << L+1 << endl; for (int i=0; i<G; i++) { for (int j=0; j<G; j++) { cout << i <<" " << j <<" " << counts[i][j] << endl; } } cout << endl;*/ } dp=vector<int>(1<<G,INF); //dp[mask] = min cost if this mask is at the beginning of the ordering dp[0] = 0; for (int mask=0; mask<1<<G; mask++) { for (int addon=0; addon<G; addon++) { if (mask&(1<<addon)) continue; int al = 0; for (int j=0; j<G; j++) { if (mask&(1<<j)) { al+=counts[addon][j]; } } //cout << mask <<" " << addon <<" " << al <<endl; dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+al); } } int self=0; for (int i=0; i<G; i++) { self+=counts[i][i]; } ans=min(ans,2*dp[(1<<G)-1]+self); long double a2 = ans; a2/=(long double)2; cout << setprecision(100) << a2 << endl; } signed main() { int local=1; if (local) { // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); } /*#ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif*/ //fast IO solve(); }

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passes.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...