oj.uz

Submission #938627

# Submission time Handle Problem Language Result Execution time Memory
938627 2024-03-05T11:27:23 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 1279 ms 342880 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 348 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 1 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 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 344 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 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 856 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 856 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 1 ms 856 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 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 1112 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 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 344 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 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 856 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 856 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 1 ms 856 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 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 1112 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 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 860 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 2 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 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 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 23 ms 23716 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 491 ms 23848 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 547 ms 23696 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 311 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 23 ms 23420 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 23 ms 23440 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 22 ms 23388 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 23 ms 23256 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 348 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 1 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 852 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 344 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 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 856 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 856 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 1 ms 856 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 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 1112 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 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 860 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 2 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 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 2 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 23 ms 23716 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 491 ms 23848 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 547 ms 23696 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 311 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 23 ms 23420 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 23 ms 23440 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 22 ms 23388 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 23 ms 23256 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 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 294 ms 3156 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 0 ms 348 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 852 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 0 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 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 2 ms 856 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 2 ms 856 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 1112 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 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 856 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 2 ms 860 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 964 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 1 ms 856 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 856 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 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 24 ms 23576 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 559 ms 23684 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 540 ms 23888 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 278 ms 23648 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 24 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 22 ms 23388 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 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 23 ms 23304 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1279 ms 342880 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1239972805.0000000000', error = '0.0000000121'
97 Halted 0 ms 0 KB -