oj.uz

Submission #938728

# Submission time Handle Problem Language Result Execution time Memory
938728 2024-03-05T13:29:39 Z LucaIlie Boarding Passes (BOI22_passes) C++17
100 / 100
 473 ms 342672 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;
vector<int> pos[MAX_G];

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 = -1, r = pos[c].size() - 1;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;

        if ( queryCost( c, mask, pos[c][mid] ) <= queryCost( c, mask, pos[c][mid + 1] ) )
            r = mid;
        else
            l = mid;
    }

    return queryCost( c, mask, pos[c][r] );
}

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 i = 0; i < g; i++ )
        pos[i].push_back( 0 );
    for ( int i = 1; i <= n; i++ )
        pos[s[i]].push_back( i );

    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;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:64:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |         pos[s[i]].push_back( i );
      |                 ^

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 600 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 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 1284 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1232 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1492 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 856 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 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 1 ms 1112 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 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 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 856 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 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 1 ms 1112 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 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 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 0 ms 344 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 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 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 1 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 856 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 2 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 15 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 15 ms 23896 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 14 ms 23644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 15 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 15 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 15 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 14 ms 23356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 15 ms 23640 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 15 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 15 ms 23388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.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 600 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 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 1284 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1232 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1492 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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 856 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 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 1 ms 1112 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 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 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 0 ms 344 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 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 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 1 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 856 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 2 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 15 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 15 ms 23896 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 14 ms 23644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 15 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 15 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 15 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 14 ms 23356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 15 ms 23640 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 15 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 15 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 65 ms 3228 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 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 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 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1232 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1232 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1492 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 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 856 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 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 1 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 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 1 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 15 ms 23644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 14 ms 23644 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 13 ms 23580 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 14 ms 23640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 15 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 14 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 15 ms 23280 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 15 ms 23388 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 15 ms 23384 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 16 ms 23644 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 473 ms 342300 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 28 ms 2652 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 458 ms 342316 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 237 ms 342148 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 44 ms 3164 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 379 ms 342380 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 423 ms 342348 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 418 ms 342396 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 428 ms 342672 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 407 ms 342352 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 415 ms 342608 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 408 ms 342312 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 270 ms 305672 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 414 ms 342348 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'