Submission #573272

#	Time	Username	Problem	Language	Result	Execution time	Memory
573272		MohamedAliSaidane	Boarding Passes (BOI22_passes)	C++14	60 / 100	2081 ms	7380 KiB

passes

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef double ld;

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second

       //#define int ll

        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        const ld MOD = 1e20;
        const int nax = 1e5 + 4;
        int n, g, sz = 1;
        ld dp[(1 << 15)][15];
        string s;
        vi A[15];
        vi st;
        ld exp_front[nax], exp_back[nax];
        void update(int i, int val)
        {
            i += sz;
            st[i] = val;
            i /= 2;
            while(i)
            {
                st[i] = st[2 * i] + st[2 * i + 1];
                i /= 2;
            }
        }
        int query(int p, int l, int r, int i, int j)
        {
            if( i>  j)
                return 0;
            if(l >= i && r <= j)
                return st[p];
            int m = (l+r)/2;
            return query(2 * p,l,m,i,min(j,m))
                + query(2 * p + 1,m+1,r,max(i,m+1),j);
        }
        ld f(int mask, int b)
        {
            if(fabs(dp[mask][b] + 1) > 1e-9)
                return dp[mask][b];
            ld rep = 0, ans = 1e20;
            for(auto e: A[b])
            {
                ld addfront = (ld)(query(1,0,sz-1,0,e));
                ld addback = (ld)(query(1,0,sz - 1,e,n-1));
                rep += min(exp_front[e] + addfront,exp_back[e] + addback);
            }
            for(auto e: A[b])
                update(e,1);
            if(mask == (1 << g)-1)
                ans = 0;
            for(int j = 0; j < g; j++)
            {
                if((1 << j) & mask)
                    continue;
                ans = min(ans,f(mask + (1 << j),j));
            }
            for(auto e: A[b])
                update(e,0);
            //cout << mask << ' ' << b << ' ' << ans << ' ' << rep  << '\n';
            return dp[mask][b] = ans + rep;
        }
        void solve()
        {
            cin >> s;
            n = s.length();
            while(sz < n)
                sz = (sz << 1);
            st.assign(2 * sz + 1,0);
            for(int i  = 0; i < n ;i ++)
            {
                int c =s[i] - 'A';
                A[c].pb(i);
                g=  max(g,c + 1);
            }
            for(int i = 0; i < (1 << g); i++)
            {
                for(int j  = 0; j < g; j++)
                    dp[i][j] =-1;
            }
            for(int group = 0; group < g; group ++)
            {
                int szi = A[group].size();
                for(int i =0; i < szi; i++)
                {
                    exp_front[A[group][i]] = (ld)(((ld)(i) * (ld)((i + 1.0)))/2.0);
                    exp_front[A[group][i]] /= (ld)(i+1.0);
                    exp_back[A[group][i]] = (ld)(((ld)((szi -i - 1.0))*(ld)((szi - i)))/2.0);
                    exp_back[A[group][i]] /= (ld)(szi - i);
                    //cout << A[group][i] << ' ' << exp_front[A[group][i]] << ' ' << exp_back[A[group][i]] << '\n';
                }
            }
            ld ans = 1e20;
            for(int i = 0; i < g; i++)
                ans = min(ans,f((1 << i),i));
            cout  << setprecision(100) <<  ans;
        }

        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt = 1;
            while(tt --)
                solve();
        }

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