oj.uz

Submission #938628

# Submission time Handle Problem Language Result Execution time Memory
938628 2024-03-05T11:28:01 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 342764 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_G = 15;
const int MAX_N = 1e5;
int n, g;
string s;
double dp[1 << MAX_G];
int frecv[MAX_G][MAX_N + 1];
long long costPref[MAX_G][MAX_G][MAX_N + 2], costSuf[MAX_G][MAX_G][MAX_N + 2];
unordered_map<char, int> lit;

double expectedInversions( int n ) {
    return (double)n * (n - 1) / 4;
}

double queryCost( int c, int mask, int i ) {
    double cost = expectedInversions( frecv[c][i] ) + expectedInversions( frecv[c][n] - frecv[c][i] );

    for ( int d = 0; d < g; d++ ) {
        if ( (mask >> d) & 1 )
            cost += costPref[c][d][i] + costSuf[c][d][i + 1];
    }

    return cost;
}

double solve( int c, int mask ) {
    int l = 0, r = n;
    while ( r - l > 2 ) {
        int mid1 = (l * 2 + r) / 3;
        int mid2 = (l + r * 2) / 3;

        if ( queryCost( c, mask, mid1 ) > queryCost( c, mask, mid2 ) )
            l = mid1;
        else if ( queryCost( c, mask, mid1 ) < queryCost( c, mask, mid2 ) )
            r = mid2;
        else {
            l++;
            r--;
        }
    }

    double bst = (double)n * n;
    for ( int i = max( 0, l - 55 ); i <= min( n, r + 55 ); i++ )
        bst = min( bst, queryCost( c, mask, i ) );

    return bst;
}

int main() {
    cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );
    
    cin >> s;
    n = s.size();
    s = " " + s;

    g = 0;
    for ( int i = 1; i <= n; i++ ) {
        if ( lit[s[i]] == 0 )
            lit[s[i]] = ++g;
        s[i] = lit[s[i]] - 1;
    }

    for ( int c = 0; c < g; c++ ) {
        for ( int i = 1; i <= n; i++ )
            frecv[c][i] = frecv[c][i - 1] + (s[i] == c);
    }
    for ( int c = 0; c < g; c++ ) {
        for ( int d = 0; d < g; d++ ) {
            if ( c == d )
                continue;

            int cnt;

            cnt = 0;
            for ( int i = 1; i <= n; i++ ) {
                costPref[c][d][i] = costPref[c][d][i - 1];
                if ( s[i] == c )
                    costPref[c][d][i] += cnt;
                if ( s[i] == d )
                    cnt++;
            }
            cnt = 0;
            for ( int i = n; i >= 1; i-- ) {
                costSuf[c][d][i] = costSuf[c][d][i + 1];
                if ( s[i] == c )
                    costSuf[c][d][i] += cnt;
                if ( s[i] == d )
                    cnt++;
            }
        }
    }

    cout << fixed << setprecision( 1 );
    for ( int mask = 1; mask < (1 << g); mask++ ) {
        dp[mask] = (double)n * n;
        for ( int c = 0; c < g; c++ ) {
            if ( (mask >> c) & 1 )
                dp[mask] = min( dp[mask], dp[mask - (1 << c)] + solve( c, mask - (1 << c) ) );
        }
    }

    cout << dp[(1 << g) - 1];

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 856 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 1016 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 856 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 856 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 856 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 856 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 0 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 30 ms 23640 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 517 ms 23688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 564 ms 23684 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 277 ms 23640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 24 ms 23316 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 25 ms 23200 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 25 ms 23440 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 29 ms 23384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 26 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 25 ms 23644 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 856 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 3 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 1016 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 856 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 2 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 856 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 856 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 856 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 0 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 30 ms 23640 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 517 ms 23688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 564 ms 23684 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 277 ms 23640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 24 ms 23316 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 25 ms 23200 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 25 ms 23440 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 29 ms 23384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 26 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 25 ms 23644 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 604 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 293 ms 3156 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 856 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 2 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 2 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 2 ms 856 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 2 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 1028 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 856 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 2 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 344 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 26 ms 23520 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 553 ms 23688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 605 ms 23696 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 325 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 26 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 30 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 25 ms 23440 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 26 ms 23440 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 35 ms 23640 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 34 ms 23440 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1669 ms 342248 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 192 ms 2816 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Execution timed out 2031 ms 342764 KB Time limit exceeded
99 Halted 0 ms 0 KB -