oj.uz

Submission #787385

# Submission time Handle Problem Language Result Execution time Memory
787385 2023-07-19T06:40:29 Z erray Boarding Passes (BOI22_passes) C++17
25 / 100
 6 ms 6472 KB 
// author: erray
#undef DEBUG 
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string S;
  cin >> S;
  int N = int(S.size());
  int G = (*max_element(S.begin(), S.end())) - 'A' + 1;
  vector<vector<int>> pref(G, vector<int>(N + 1));
  vector<vector<int>> occ(G);            
  vector<vector<vector<long long>>> contrib(G, vector<vector<long long>>(G, vector<long long>(N + 1)));
  for (int l = 0; l < G; ++l) {
    for (int i = 0; i < N; ++i) {
      bool me = S[i] == ('A' + l);
      if (me) {
        occ[l].push_back(i);
      }
      pref[l][i + 1] = pref[l][i] + me;      
    }
  }
  for (int l = 0; l < G; ++l) {
    for (int i = 0; i < N; ++i) {
      bool me = S[i] == ('A' + l);      
      for (int j = 0; j < G; ++j) {
        contrib[j][l][i + 1] = contrib[j][l][i];
        if (me) {
          contrib[j][l][i + 1] += pref[j][i];
        }
      }
    }
  }
  debug(pref, contrib);
  auto Sq = [&](int x) {
    return 1LL * x * (x - 1) / 2;
  };
  vector<long long> best(1 << G, 1LL * N * N);
  best[0] = 0;
  vector<int> lg(1 << G);
  for (int m = 0; m < (1 << G); ++m) {
    if (m > 0) { lg[m] = __lg(m); }
    for (int i = 0; i < G; ++i) {
      if ((m >> i) % 2 == 0) {
        auto E = [&](int s) {
          int x = 0;
          if (s > 0) {
            x = occ[i][s - 1] + 1;
          }
          int cm = m;
          long long res = 0;
          while (cm > 0) {
            int l = lg[cm];
            debug(l, i);
            long long add = 2 * (contrib[l][i][x] + (contrib[i][l][N] - contrib[i][l][x] - 1LL * s * (pref[l][N] - pref[l][x]))); 
            assert(add >= 0);
            res += add;
            cm ^= 1 << l;
          } 
          res += Sq(s) + Sq(pref[i][N] - s);
          return res;
        };
        int low = 0, high = int(occ[i].size());
        while (low < high) {
          int mid = (low + high) >> 1;
          debug(mid, E(mid), E(mid + 1));
          if (E(mid) > E(mid + 1)) {
            low = mid + 1;
          } else {
            high = mid;
          }
        }
        debug(m, i, low, E(low));
        int next = m | (1 << i);
        best[next] = min(best[next], best[m] + E(low));   
      }
    }
  }
  cout << (long double) 0.5 * best[(1 << G) - 1] << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 324 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 324 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 328 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 316 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 4 ms 6356 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 6 ms 6472 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -