Submission #949904

#	Time	Username	Problem	Language	Result	Execution time	Memory
949904		Dec0Dedd	Boarding Passes (BOI22_passes)	C++14	100 / 100	232 ms	96952 KiB

passes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, int> pii;

const int N = 1e5+100;
const ll INF = 1e18;
const int G = 15;

vector<int> idx[N];

ll n, cross[G][G][N];
string s;

ll dist[1<<G];

ll nc2(ll x) {
    if (x < 2) return 0;
    return x*(x-1)/2;
}

ll calc(int msk, int u, int k) {
    ll res=0;
    for (int i=0; i<G; ++i) {
        if (!(msk&(1<<i))) continue;
        res+=2*cross[u][i][k];
    } int sz=idx[u].size();
    res+=nc2(k)+nc2(sz-k);
    return res;
}

// cost to go MSK -> MSK^u
ll cost(int msk, int u) {
    ll sz=idx[u].size();

    int l=0, r=sz-1, res=0;
    while (l <= r) {
        int m=(l+r)/2;
        if (calc(msk, u, m) > calc(msk, u, m+1)) res=m+1, l=m+1;
        else r=m-1;
    } return min(calc(msk, u, 0), calc(msk, u, res));
}

void solve() {
    cin>>s;
    n=s.size();

    for (int i=0; i<n; ++i) idx[s[i]-'A'].push_back(i+1);

    for (int a=0; a<G; ++a) {
        for (int b=0; b<G; ++b) {
            if (a == b) continue;
            ll ps[n+1]={};

            for (auto u : idx[b]) ++ps[u];
            for (int i=1; i<=n; ++i) ps[i]+=ps[i-1];
            int sz=idx[a].size();

            ll psum=0, ssum=0;
            for (auto x : idx[a]) ssum+=(ps[n]-ps[x-1]);
            cross[a][b][0]=ssum;

            for (int i=1; i<=sz; ++i) {
                int x=idx[a][i-1];
                psum+=ps[x], ssum-=(ps[n]-ps[x-1]);
                cross[a][b][i]=psum+ssum;
            }
        }
    }

    for (int i=0; i<(1<<G); ++i) dist[i]=INF;
    dist[0]=0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        pii x=pq.top(); pq.pop();
        ll d=x.first;
        int msk=x.second;

        if (dist[msk] < d) continue;
        for (int i=0; i<G; ++i) {
            if (msk&(1<<i)) continue;

            if (dist[msk^(1<<i)] > dist[msk]+cost(msk, i)) {
                dist[msk^(1<<i)]=dist[msk]+cost(msk, i);
                pq.push({dist[msk^(1<<i)], msk^(1<<i)});
            }
        }
    } assert(dist[(1<<G)-1] < INF);

    cout<<dist[(1<<G)-1]/2;
    if (dist[(1<<G)-1]%2) cout<<".5\n";
    else cout<<"\n";
}

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

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