oj.uz

Submission #938625

# Submission time Handle Problem Language Result Execution time Memory
938625 2024-03-05T11:26:53 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 1226 ms 343056 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 + 20 ); 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 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 1108 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 852 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 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 3 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 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 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 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 2 ms 840 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 2 ms 856 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 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 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 3 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 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 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 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 2 ms 840 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 2 ms 856 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 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 500 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 1072 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 2 ms 856 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 2 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 864 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 864 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 868 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 26 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 514 ms 23696 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 585 ms 23692 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 279 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 25 ms 23440 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 24 ms 23252 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 24 ms 23388 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 24 ms 23428 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 23 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 23 ms 23388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 1108 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 852 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 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 3 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 860 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 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 2 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 2 ms 840 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 2 ms 856 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 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 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 500 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 1072 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 2 ms 856 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 2 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 864 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 2 ms 864 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 2 ms 868 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 26 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 514 ms 23696 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 585 ms 23692 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 279 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 25 ms 23440 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 24 ms 23252 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 24 ms 23388 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 24 ms 23428 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 23 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 23 ms 23388 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 300 ms 3264 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 600 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 3 ms 856 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 600 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 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 856 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 856 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 860 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 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 856 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 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 540 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 23 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 517 ms 23688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 532 ms 23692 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 281 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 22 ms 23384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 23 ms 23384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 23 ms 23384 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 23 ms 23388 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 23 ms 23384 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 23 ms 23388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1226 ms 343056 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1239972805.0000000000', error = '0.0000000121'
97 Halted 0 ms 0 KB -