Submission #938728

#	Time	Username	Problem	Language	Result	Execution time	Memory
938728		LucaIlie	Boarding Passes (BOI22_passes)	C++17	100 / 100	473 ms	342672 KiB

passes

#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 (stderr)

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 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40