oj.uz

Submission #938632

# Submission time Handle Problem Language Result Execution time Memory
938632 2024-03-05T11:30:22 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 1453 ms 343400 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 + (r - l) / 3;
        int mid2 = r - (r - l) / 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++;
    }

    double bst = (double)n * n;
    for ( int i = max( 0, l - 20 ); i <= min( n, r + 50 ); 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 916 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 936 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 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 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 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 972 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 2 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 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 0 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 2 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 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 972 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 2 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 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 976 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 872 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 1 ms 860 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 544 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 26 ms 23640 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 839 ms 23952 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1018 ms 23716 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 330 ms 23656 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 25 ms 23384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 25 ms 23388 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 29 ms 23440 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 31 ms 23332 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 25 ms 23452 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 916 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 936 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 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 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 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 972 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 2 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 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 976 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 872 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 1 ms 860 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 544 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 26 ms 23640 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 839 ms 23952 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 1018 ms 23716 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 330 ms 23656 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 25 ms 23384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 25 ms 23388 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 29 ms 23440 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 31 ms 23332 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 25 ms 23452 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 355 ms 3380 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 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 1 ms 344 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 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1112 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1108 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1112 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 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 3 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 856 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 2 ms 856 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 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 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 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 0 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 25 ms 23724 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 847 ms 23960 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 1008 ms 23700 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 327 ms 23888 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 24 ms 23384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 25 ms 23384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 24 ms 23448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 25 ms 23452 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 24 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 25 ms 23452 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1453 ms 343400 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1239972811.0000000000', error = '0.0000000169'
97 Halted 0 ms 0 KB -