oj.uz

Submission #593109

# Submission time Handle Problem Language Result Execution time Memory
593109 2022-07-10T12:14:07 Z MilosMilutinovic Boarding Passes (BOI22_passes) C++14
0 / 100
 391 ms 852 KB 
/**
 *    author:  wxhtzdy
 *    created: 10.07.2022 13:22:51
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  string s;
  cin >> s;
  int n = (int) s.size();
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = (int) (s[i] - 'A');
  }
  const int A = 15;
  vector<vector<int>> ids(A);
  for (int i = 0; i < n; i++) {
    ids[a[i]].push_back(i);
  }
  vector<vector<vector<int>>> cntL(A, vector<vector<int>>(A));
  vector<vector<vector<int>>> cntR(A, vector<vector<int>>(A));
  for (int i = 0; i < A; i++) {
    int sz = (int) ids[i].size();
    for (int j = 0; j < A; j++) {
      cntL[i][j].resize(sz);
      int ptr = 0;         
      for (int k = 0; k < sz; k++) {                  
        while (ptr < (int) ids[j].size() && ids[j][ptr] < ids[i][k]) {
          ptr += 1;
        }
        cntL[i][j][k] = ptr;
      }
    }
  }                    
  for (int i = 0; i < A; i++) {
    int sz = (int) ids[i].size();
    for (int j = 0; j < A; j++) {
      cntR[i][j].resize(sz);
      int ptr = (int) ids[j].size() - 1;         
      for (int k = sz - 1; k >= 0; k--) {                  
        while (ptr >= 0 && ids[j][ptr] > ids[i][k]) {
          ptr -= 1;
        }
        cntR[i][j][k] = (int) ids[j].size() - 1 - ptr;
      }
    }
  }                    
  vector<long double> dp(1 << A, 1e14);
  dp[0] = 0;
  for (int s = 0; s < (1 << A); s++) {
    for (int i = 0; i < A; i++) {
      if (s >> i & 1) {
        continue;
      }
      if (ids[i].empty()) {
        dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s]);
        continue;
      }
      auto Calc = [&](int id) {
        int L = id + 1;
        int R = (int) ids[i].size() - id - 1;
        long double res = (long double) (L * 1LL * (L - 1) / 2 + R * 1LL * (R - 1) / 2) / 2.0;
        for (int j = 0; j < A; j++) {
          if (s >> j & 1) {
            if (id >= 0) {
              res += cntL[i][j][id];
            }
            if (id + 1 < (int) ids[i].size()) {
              res += cntR[i][j][id + 1];
            }
          }
        }
        return res;
      };  
      /*int low = -1, high = (int) ids[i].size() - 2, at = high + 1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        if (Calc(mid) > Calc(mid + 1)) {
          low = mid + 1;
        } else {
          at = mid;
          high = mid - 1;
        }
      }*/
      for (int p = -1; p < (int) ids[i].size(); p++) {
        dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s] + Calc(p));      
      }
    } 
  }                                        
  cout << fixed << setprecision(7) << dp[(1 << A) - 1] << '\n';
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 391 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 391 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -