Submission #666591

#	Time	Username	Problem	Language	Result	Execution time	Memory
666591		mychecksedad	Boarding Passes (BOI22_passes)	C++17	100 / 100	391 ms	27344 KiB

passes

/* Author : Mychecksdead */ 
#include<bits/stdc++.h>
using namespace std;
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e5 + 100, K = 15;

int n;
long long pref[K][K][N], suf[K][K][N];
string s;
double dp[N];
vector<int> v[K], vis;

void solve(){
    // freopen("in.txt", "r", stdin);
    cin >> s; n = s.length();

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

    for(int i = 0; i < (1<<K); ++i) dp[i] = 1e15;

    dp[0] = 0;

    for(int i = 0; i < K; ++i){
        for(int j = 0; j < K; ++j){

            for(int k = 0; k <= v[i].size() + 1; ++k) pref[i][j][k] = suf[i][j][k] = 0;
            
            int cur = 0;
            double sum = 0;
            
            for(int k = 0; k <= v[i].size(); ++k){
                while(k > 0 && cur < v[j].size() && v[j][cur] < v[i][k - 1]){
                    cur++;
                }
                sum += cur;
                pref[i][j][k] = sum;
            }
            cur = v[j].size() - 1;
            sum = 0;
            for(int k = v[i].size(); k >= 1; --k){
                while(cur >= 0 && v[j][cur] > v[i][k - 1]){
                    cur--;
                }
                sum += v[j].size() - cur - 1;
                suf[i][j][k] = sum;
            }
        }
    }


    for(int mask = 1; mask < (1<<K); ++mask){
        vector<int> p;
        for(int j = 0; j < K; ++j){
            if(mask&(1<<j)){
                p.push_back(j);
            }
        }
        int s = p.size();
        for(int i = 0; i < s; ++i){
            int S = v[p[i]].size();
            int l = 0, r = S;
            long long sum = 0;
            while(l <= r){
                int m1 = l + (r-l)/3, m2 = r - (r-l)/3;
                double val1 = 0, val2 = 0;
                for(int j = 0; j < s; ++j){
                    long long L = 1;
                    if(i != j) L = 2;
                    
                    val1 += (pref[p[i]][p[j]][m1] + suf[p[i]][p[j]][m1 + 1]) * L;
                    val2 += (pref[p[i]][p[j]][m2] + suf[p[i]][p[j]][m2 + 1]) * L;
                }

                sum = min(val1, val2);

                if(val1 > val2){
                    l = m1 + 1;
                }else if(val2 > val1){
                    r = m2 - 1;
                }else{
                    l = m1 + 1, r = m2 - 1;
                }

            }
            
            dp[mask] = min(dp[mask], dp[mask^(1<<p[i])] + sum);
        }
    }


    cout << dp[(1<<K)-1] / 2.0;
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    setp();
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message (stderr)

passes.cpp: In function 'void solve()':
passes.cpp:27:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for(int k = 0; k <= v[i].size() + 1; ++k) pref[i][j][k] = suf[i][j][k] = 0;
      |                            ~~^~~~~~~~~~~~~~~~~~
passes.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int k = 0; k <= v[i].size(); ++k){
      |                            ~~^~~~~~~~~~~~~~
passes.cpp:33:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 while(k > 0 && cur < v[j].size() && v[j][cur] < v[i][k - 1]){
      |                                ~~~~^~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:99:16: warning: unused variable 'aa' [-Wunused-variable]
   99 |     int T = 1, aa;
      |                ^~

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