Submission #709941

#	Time	Username	Problem	Language	Result	Execution time	Memory
709941		aryan12	Boarding Passes (BOI22_passes)	C++17	30 / 100	2082 ms	3852 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    string s;
    cin >> s;
    int n = s.size();
    int a[n], maxx = 0;
    map<int, int> cc;
    for(int i = 0; i < n; i++)
    {
        a[i] = s[i] - 'A';
        cc[a[i]] = 1;
    }
    int cnt = 0;
    for(auto i: cc)
    {
        cc[i.first] = cnt++;
    }
    for(int i = 0; i < n; i++)
    {
        a[i] = cc[a[i]];
        maxx = max(maxx, a[i]);
    }
    vector<int> perm;
    double ans = 1e18;
    for(int i = 0; i <= maxx; i++)
    {
        perm.push_back(i);
    }
    do
    {
        vector<bool> visited(n, false);
        double final_ans = 0.0;
        // cout << "----------------------------\n";
        // cout << perm[0] << " " << perm[1] << " " << perm[2] << " " << perm[3] << " " << perm[4] << "\n";
        for(int cur_idx = 0; cur_idx < perm.size(); cur_idx++)
        {
            // cout << "cur_idx = " << cur_idx << "\n";
            vector<int> indices;
            for(int j = 0; j < n; j++)
            {
                if(perm[cur_idx] == a[j])
                {
                    indices.push_back(j);
                }
            }
            int siz = indices.size();
            vector<int> prefix_impact(siz, 0), suffix_impact(siz, 0);
            int cnt = 0, pos = 0;
            for(int i = 0; i < n; i++)
            {
                if(visited[i])
                {
                    cnt++;
                }
                if(pos != siz && i == indices[pos])
                {
                    pos++;
                    prefix_impact[pos - 1] = cnt;
                }
            }
            // cout << "prefix_impact\n";
            // for(int i = 0; i < siz; i++)
            // {
            //     cout << prefix_impact[i] << " ";
            // }
            // cout << "\n";
            // cout << "suffix_impact\n";
            // for(int i = 0; i < siz; i++)
            // {
            //     cout << suffix_impact[i] << " ";
            // }
            // cout << "\n";
            cnt = 0;
            pos = siz - 1;
            int current_independent = 0;
            for(int i = n - 1; i >= 0; i--)
            {
                if(visited[i])
                {
                    cnt++;
                }
                if(pos != -1 && i == indices[pos])
                {
                    pos--;
                    suffix_impact[pos + 1] = cnt;
                    current_independent += cnt;
                }
            }
            double cur_ans = current_independent;
            double siz_d = siz;
            cur_ans = (cur_ans + (siz_d * (siz_d - 1)) / 4);
            // cout << "a1 = " << 0 << ", a2 = " << siz_d << ", cur_ans = " << cur_ans << ", not depend = " << current_independent << "\n";
            double holy_ans = cur_ans;
            // cout << "cur_ans = " << cur_ans << "\n";
            for(int x = 0; x < indices.size(); x++)
            {
                cur_ans = 0;
                current_independent = current_independent - suffix_impact[x] + prefix_impact[x];
                cur_ans = current_independent;
                // cout << "current_independent = " << current_independent << "\n";
                int y = indices.size();
                double a1 = x + 1;
                double a2 = y - a1;
                cur_ans = cur_ans + (a1 * (a1 - 1)) / 4.00;
                if(a2 != 0)
                {
                    cur_ans = cur_ans + (a2 * (a2 - 1)) / 4.00;
                }
                // cout << "a1 = " << a1 << ", a2 = " << a2 << ", cur_ans = " << cur_ans << ", not depend = " << current_independent << "\n";
                holy_ans = min(holy_ans, cur_ans);
            }
            // cout << "finally adding: " << holy_ans << "\n";
            final_ans += holy_ans;
            for(int i = 0; i < siz; i++)
            {
                // cout << "indices[i] = " << indices[i] << "\n";
                visited[indices[i]] = true;
            }
        }
        // cout << "final_ans = " << final_ans << "\n";
        // cout << perm[0] << " " << perm[1] << " " << perm[2] << " " << perm[3] << " " << perm[4] << "\n";
        // cout << "----------------------------\n";
        ans = min(ans, final_ans);
    } while(next_permutation(perm.begin(), perm.end()));
    cout << fixed << setprecision(10) << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'void Solve()':
passes.cpp:42:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int cur_idx = 0; cur_idx < perm.size(); cur_idx++)
      |                              ~~~~~~~~^~~~~~~~~~~~~
passes.cpp:102:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for(int x = 0; x < indices.size(); x++)
      |                            ~~^~~~~~~~~~~~~~~~

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