oj.uz

Submission #938707

# Submission time Handle Problem Language Result Execution time Memory
938707 2024-03-05T13:02:47 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 1406 ms 343044 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 - 10 ); i <= min( n, r + 10 ); 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++;
            }
        }
    }

    for ( int mask = 1; mask < (1 << g); mask++ )
        dp[mask] = (double)n * n;

    cout << fixed << setprecision( 1 );
    for ( int mask = 1; mask < (1 << g); mask++ ) {
        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 456 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 600 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 1112 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1108 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1112 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 980 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 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 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 2 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 856 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 0 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 980 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 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 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 2 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 856 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 1 ms 976 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 856 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 2 ms 900 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 2 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 856 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 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 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 1 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 23708 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1072 ms 23892 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1312 ms 23892 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 438 ms 23892 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 23 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 24 ms 23388 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 24 ms 23388 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 24 ms 23456 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 456 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 600 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 1112 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1108 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1112 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 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 980 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 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 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 2 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 2 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 856 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 1 ms 976 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 856 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 2 ms 900 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 2 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 856 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 2 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 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 1 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 23708 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 1072 ms 23892 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 1312 ms 23892 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 438 ms 23892 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 23 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 24 ms 23388 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 24 ms 23388 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 24 ms 23456 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 403 ms 3164 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 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 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 984 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 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 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 860 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 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 856 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 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 972 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 27 ms 23536 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 1070 ms 23704 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 1328 ms 23704 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 432 ms 23640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 27 ms 23384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 24 ms 23448 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 23460 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 24 ms 23388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1406 ms 343044 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1239972811.0000000000', error = '0.0000000169'
97 Halted 0 ms 0 KB -