Submission #593133

#	Time	Username	Problem	Language	Result	Execution time	Memory
593133		MilosMilutinovic	Boarding Passes (BOI22_passes)	C++14	100 / 100	242 ms	25632 KiB

passes

/**
 *    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<long long>>> cntL(A, vector<vector<long long>>(A));
  vector<vector<vector<long long>>> cntR(A, vector<vector<long long>>(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;
        if (k > 0) {
          cntL[i][j][k] += cntL[i][j][k - 1];
        }
      }
    }
  }                    
  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;
        if (k < sz - 1) {
          cntR[i][j][k] += cntR[i][j][k + 1];
        }
      }
    }
  }                    
  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 = (double) (L * 1LL * (L - 1) / 2) / 2.0; 
        res += (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;
        }
      }
      dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s] + Calc(at));      
    } 
  }
  int zzz = dp[(1 << A) - 1];
  if (dp[(1 << A) - 1] != (double) zzz) {
    cout << fixed << setprecision(1) << dp[(1 << A) - 1];
  } else {
    cout << fixed << setprecision(0) << dp[(1 << A) - 1];
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40