Submission #666575

#	Time	Username	Problem	Language	Result	Execution time	Memory
666575		mychecksedad	Boarding Passes (BOI22_passes)	C++17	0 / 100	23 ms	3156 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;
double pref[K][K][N], suf[K][K][N];
string s;
double dp[N];
vector<int> v[K], vis;

void solve(){
    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){
            if(i == j) continue;

            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 + k * (k-1) / 4.0;
            }
            cur = v[j].size();
            sum = 0;
            for(int k = v[i].size(); k >= 1; --k){
                while(cur - 1 >= 0 && v[j][cur - 1] > v[i][k - 1]){
                    cur--;
                }
                sum += v[j].size() - cur;
                long long s = v[i].size() - k + 1;
                suf[i][j][k] = sum + s * (s-1) / 4.0;
            }
        }
    }


    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[i].size();
            int l = 0, r = S;
            double 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){
                    if(i==j) continue;
                    val1 += pref[p[i]][p[j]][m1] + suf[p[i]][p[j]][m1 + 1];
                    val2 += pref[p[i]][p[j]][m2] + suf[p[i]][p[j]][m2 + 1];
                }

                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];
}



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:98:16: warning: unused variable 'aa' [-Wunused-variable]
   98 |     int T = 1, aa;
      |                ^~

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