Submission #1104986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104986		koukirocks	Boarding Passes (BOI22_passes)	C++17	100 / 100	1028 ms	707196 KiB

passes

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

ldb pas[15][15][MAX],rpas[15][15][MAX];
vector<int> pos[20];
int g;

ldb calc(ldb x,int st,int can) {
    ldb ans=0;
    ll k=(x?pos[can][x-1]:0);
    // cout<<x<<" "<<k<<" xk\n";
    for (int i=0;i<g;i++) {
        if (st&(1<<i)) {
            ans+=pas[i][can][k]+rpas[i][can][k+1];
        }
    }
    ldb n = pos[can].size();
    return ans+x*(x-1)/4+(n-x)*(n-x-1)/4;
}

int main() {
    speed;
    string s;
    cin>>s;
    vector<int> d;
    for (char c:s) d.push_back(c);
    sort(all(d));
    d.resize(unique(all(d))-d.begin());
    int n=s.size();
    for (int i=0;i<n;i++) {
        pos[lower_bound(all(d),s[i])-d.begin()].push_back(i);
    }
    g=d.size();
    // for (int i=0;i<g;i++) {
    //     for (int j:pos[i]) cout<<j<<" ";
    //     cout<<" pos\n";
    // }
    // cout<<"g "<<g<<"\n";
    for (int i=0;i<g;i++) {
        for (int j=0;j<g;j++) {
            int iid=0,jid=0;
            pas[i][j][0]=0;
            ll cnt=0;
            for (int k=0;k<n;k++) {
                if (iid<pos[i].size() and pos[i][iid]==k) {
                    cnt++;
                    iid++;
                }
                if (jid<pos[j].size() and pos[j][jid]==k) {
                    if (k>0) pas[i][j][k]=pas[i][j][k-1]+cnt;
                    jid++;
                } else pas[i][j][k]=pas[i][j][k-1];
                // cout<<i<<" "<<j<<" "<<k<<" "<<iid<<" "<<jid<<" "<<cnt<<" "<<pas[i][j][k]<<" pas\n";
            }
        }
    }
    for (int i=0;i<g;i++) {
        for (int j=0;j<g;j++) {
            int iid=pos[i].size()-1,jid=pos[j].size()-1;
            rpas[i][j][n]=0;
            ll cnt=0;
            for (int k=n-1;k>=0;k--) {
                if (iid>=0 and pos[i][iid]==k) {
                    cnt++;
                    iid--;
                }
                if (jid>=0 and pos[j][jid]==k) {
                    rpas[i][j][k]=rpas[i][j][k+1]+cnt;
                    jid--;
                } else rpas[i][j][k]=rpas[i][j][k+1];
            }
        }
    }
    ldb dp[1<<16];
    for (int st=1;st<(1<<g);st++) dp[st]=oo;
    dp[0]=0;
    for (int st=0;st<(1<<g);st++) {
        for (int i=0;i<g;i++) {
            if (st&(1<<i)) continue;
            int l=0,r=pos[i].size();
            // cout<<l<<" "<<r<<" l r\n";
            while (l+2<r) {
                ldb mid1=(l+r)/2;
                ldb mid2=mid1+1;
                // cout<<st<<" "<<i<<" st can\n";
                // cout<<mid1<<" "<<calc(mid1,st,i)<<" mid1\n";
                // cout<<mid2<<" "<<calc(mid2,st,i)<<" mid2\n";
                if (calc(mid1,st,i)<calc(mid2,st,i)) r=mid2;
                else l=mid1;
            }
            for (ldb k=l;k<=r;k++) {
                // cout<<k<<" "<<calc(k,st,i)<<" k calc\n";
                dp[st|(1<<i)]=min(dp[st|(1<<i)],dp[st]+calc(k,st,i));
            }
        }
    }
    cout<<setprecision(100)<<dp[(1<<g)-1]<<"\n";
    return 0;
}

// HEHEHEHIHILOL

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 if (iid<pos[i].size() and pos[i][iid]==k) {
      |                     ~~~^~~~~~~~~~~~~~
passes.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 if (jid<pos[j].size() and pos[j][jid]==k) {
      |                     ~~~^~~~~~~~~~~~~~

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