Submission #1067158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067158		mispertion	Boarding Passes (BOI22_passes)	C++17	100 / 100	396 ms	52488 KiB

passes

#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = 1e16;
const int P = 2;

int mult(int a, int b){
    return a * 1LL * b % mod;
}

int sum(int a, int b){
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

int binpow(int a, int n){
    if (n == 0)
        return 1;
    if (n % 2 == 1){
        return mult(binpow(a, n - 1), a);
    }
    else{
        auto b = binpow(a, n / 2);
        return mult(b, b);
    }
}

const int K = 15;

int n, k, a[N], pr[K][N], sf[K][N], prr[K][K][N], sff[K][K][N];
ld dp[N];
vector<int> pos[K];

void solve(){
    string s = "";
    cin >> s;
    n = sz(s);
    vector<int> al = {};
    for(auto e : s){
        al.pb(e - 'A');
    }
    sort(all(al));
    al.resize(unique(all(al)) - al.begin());
    k = sz(al);
    for(int i = 0; i < k; i++)
        pos[i] = {0};
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(all(al), s[i - 1] - 'A') - al.begin();
        pos[a[i]].pb(i);
        pr[a[i]][i] = 1;
        sf[a[i]][i] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int x = 0; x < k; x++)
            pr[x][i] += pr[x][i - 1];
    for(int i = n; i >= 1; i--)
        for(int x = 0; x < k; x++)
            sf[x][i] += sf[x][i + 1];
    for(int y = 0; y < k; y++){
        for(int x = 0; x < k; x++){
            if(x == y) continue;
            for(int m = 1; m < sz(pos[x]); m++)
                prr[y][x][m] = prr[y][x][m - 1] + pr[y][pos[x][m]];
            for(int m = sz(pos[x]) - 1; m >= 1; m--)
                sff[y][x][m] = sff[y][x][m + 1] + sf[y][pos[x][m]];
        }
    }
    for(int mask = 1; mask < (1 << k); mask++){
        dp[mask] = infi;
        for(int x = 0; x < k; x++){
            if(!((mask >> x) & 1)) continue;
            int lo = 0, hi = sz(pos[x]) - 1;
            while(lo + 2 < hi){
                ld m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
                ld s1 = (m1 * (m1 - 1)) / 4.0 + (((ld)sz(pos[x]) - m1 - 1) * (((ld)sz(pos[x]) - m1 - 2))) / 4.0;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s1 += prr[y][x][(int)m1];
                    s1 += sff[y][x][(int)m1 + 1];
                }
                ld s2 = (m2 * (m2 - 1)) / 4.0 + (((ld)sz(pos[x]) - m2 - 1) * (((ld)sz(pos[x]) - m2 - 2))) / 4.0;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s2 += prr[y][x][(int)m2];
                    s2 += sff[y][x][(int)m2 + 1];
                }
                if(s1 > s2){
                    lo = m1;
                }else{
                    hi = m2;
                }
            }
            for(ld m1 = lo; m1 <= hi; m1 += 1){
                ld s1 = (m1 * (m1 - 1)) / 4.0 + (((ld)sz(pos[x]) - m1 - 1) * (((ld)sz(pos[x]) - m1 - 2))) / 4.0;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s1 += prr[y][x][(int)m1];
                    s1 += sff[y][x][(int)m1 + 1];
                }
                dp[mask] = min(dp[mask], s1 + dp[mask ^ (1 << x)]);
            }
        }
    }
    cout << fixed << setprecision(10) << dp[(1 << k) - 1] << '\n';
}

signed main(){
    mispertion;
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40