oj.uz

Submission #629571

# Submission time Handle Problem Language Result Execution time Memory
629571 2022-08-14T15:52:07 Z _martynas Boarding Passes (BOI22_passes) C++11
25 / 100
 46 ms 852 KB 
#include <bits/stdc++.h>
 
using namespace std;
using namespace std::chrono;
 
using ll = long long;
 
const int MXG = 15;
const ll INF = 1e17;
 
string s;
int n;
vector<ll> A[MXG];
// pref[i][j][k] -> i after j cost from left at k
vector<ll> pref[MXG][MXG];
// suff[i][j][k] -> i after j cost from right at k
vector<ll> suff[MXG][MXG];
ll dp[1 << MXG];
bool visited[1 << MXG];
 
// vector.insert(vector.begin(), x) 100x slower than vector.push_back(x)...
void init()
{
    // pref
    for(int i = 0; i < MXG; i++) {
        for(int j = 0; j < MXG; j++) {
            if(i == j || A[i].empty() || A[j].empty()) continue;
            int r = 0;
            int cost = 0;
            for(int k = 0; k < A[i].size(); k++) {
                while(r < A[j].size() && A[j][r] < A[i][k]) {
                    r++;
                }
                cost += r;
                pref[i][j].push_back(4*cost);
            }
        }
    }
    // suff
    for(int i = 0; i < MXG; i++) {
        for(int j = 0; j < MXG; j++) {
            if(i == j || A[i].empty() || A[j].empty()) continue;
            int r = A[j].size()-1;
            int cost = 0;
            for(int k = A[i].size()-1; k >= 0; k--) {
                while(r >= 0 && A[j][r] > A[i][k]) {
                    r--;
                }
                cost += A[j].size()-1-r;
                suff[i][j].push_back(4*cost);
            }
            reverse(suff[i][j].begin(), suff[i][j].end());
        }
    }
}
 
ll cost(int group, int bitmask, int split)
{
    ll sum = 0;
    for(int g = 0; g < MXG; g++) {
        if(((bitmask >> g) & 1) == 0 || A[g].empty() || g == group) continue;
        //cerr << "left: " << (split > -1 ? pref[group][g][split] : 0) << "\n";
        sum += split > -1 ? pref[group][g][split] : 0;
        //cerr << "right: " << (split+1 < A[group].size() ? suff[group][g][split+1] : 0) << "\n";
        sum += split+1 < A[group].size() ? suff[group][g][split+1] : 0;
    }
    if(split > 0) {
        //cerr << "left chance: " << split*(split+1) << "\n";
        // int*int overflow LET'S GO!
        sum += 1LL*split*(split+1); // chance to collide between on the left
    }
    ll cnt = A[group].size() - (split+1);
    if(cnt > 1) {
        //cerr << "right chance: " << cnt*(cnt-1) << "\n";
        sum += cnt*(cnt-1); // chance to collide between on the right
    }
    return sum;
}
 
ll recur(int bitmask)
{
    if(bitmask == 0) {
        return 0;
    }
    if(visited[bitmask]) {
        return dp[bitmask];
    }
    visited[bitmask] = true;
    ll mn = INF;
    for(int g = 0; g < MXG; g++) {
        if(((bitmask >> g) & 1) == 0) continue;
        int bits = bitmask - (1 << g);
        ll initial = recur(bits);
        if(A[g].empty()) {
            mn = min(mn, initial);
            continue;
        }
        int l = -1, r = A[g].size()-1;
        while(l < r) {
            int mid = l == -1 && r == 0 ? -1 : (l + r) / 2;
            ll a = cost(g, bits, mid);
            ll b = cost(g, bits, mid+1);
            if(a < b) {
                r = mid;
            }
            else {
                l = mid+1;
            }
        }
        mn = min(mn, initial + cost(g, bits, l));
    }
    dp[bitmask] = mn;
    return dp[bitmask];
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    getline(cin, s);
    n = s.size();
 
    for(int i = 0; i < n; i++) {
        A[s[i]-'A'].push_back(i);
    }
    init();
    double ans = recur(0x7fff);
    cout << ans / 4;
 
    return 0;
}
/*
AACCAA
HEHEHEHIHILOL
ONMLKJIHGFEDCBAABCDEFGHIJKLMNO
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 
*/

Compilation message

passes.cpp: In function 'void init()':
passes.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int k = 0; k < A[i].size(); k++) {
      |                            ~~^~~~~~~~~~~~~
passes.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 while(r < A[j].size() && A[j][r] < A[i][k]) {
      |                       ~~^~~~~~~~~~~~~
passes.cpp: In function 'll cost(int, int, int)':
passes.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         sum += split+1 < A[group].size() ? suff[group][g][split+1] : 0;
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 596 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 8 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 7 ms 624 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 34 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 36 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 21 ms 636 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 21 ms 608 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 28 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 608 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 24 ms 592 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 25 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 25 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 26 ms 592 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 27 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 26 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 7 ms 624 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 34 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 36 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 21 ms 636 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 21 ms 608 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 28 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 608 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 24 ms 592 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 25 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 25 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 26 ms 592 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 27 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 26 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 10 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 10 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 46 ms 620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 37 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 636 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 18 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 29 ms 616 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 24 ms 632 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 27 ms 628 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 25 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 25 ms 632 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 25 ms 628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 26 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 28 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 25 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 29 ms 608 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 29 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 13 ms 852 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 13 ms 852 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 11 ms 596 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -