Submission #748665

#	Time	Username	Problem	Language	Result	Execution time	Memory
748665		inventiontime	Boarding Passes (BOI22_passes)	C++17	5 / 100	5 ms	1680 KiB

passes

    #include <bits/stdc++.h>
    using namespace std;
     
    #define int ll
    #define endl '\n' //comment for interactive
    #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
     
    #define pb push_back
    #define re resize
    #define ff first
    #define ss second
     
    #define all(x) (x).begin(), (x).end()
    #define all1(x) (x).begin()+1, (x).end()
    #define loop(i, n) for(int i = 0; i < n; i++)
    #define loop1(i, n) for(int i = 1; i <= n; i++)
     
    #define print(x) cout << #x << ": " << x << endl << flush
     
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<double> vd;
    typedef array<int, 2> ii;
    typedef array<int, 3> ti;
    typedef vector<ii> vii;
    typedef vector<ti> vti;
    typedef vector<vi> vvi;
    typedef priority_queue<int> pq;
     
    template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
    template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }
     
    const int inf = 1e17;
     
    double cst(int x) {
        return (double) x * (x-1) / 4;
    }
     
    void solve() {
     
     
        string s;
        cin >> s;
        int n = s.size();
        vvi pos(26);
        loop(i, n) 
            pos[s[i]-'A'].pb(i);
        vi ch;
        loop(i, 26) if(!pos[i].empty())
            ch.pb(i);
        int g = ch.size();
        vi id(26);
        loop(i, g) id[ch[i]] = i;
     
        if(g == 1) {
            cout << setprecision(16) << cst(n/2) + cst((n+1)/2) << endl;
            return;
        }
     
     
        vd dp(1 << g, inf);
        dp[0] = 0;

        auto cost = [&] (int pre, int ch, int idx) -> double {
            bitset<15> prev(pre);
            double ans = 0;
            int cnt = 0, oth = 0;
            for(int i = 0; i <= idx; i++) {
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    ans += oth;
                }
            }
            ans += cst(cnt);

            cnt = 0, oth = 0;
            for(int i = n-1; i > idx; i--) {
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    ans += oth;
                }
            }
            ans += cst(cnt);
            return ans;
        };

        loop(pre, 1 << g) {
            bitset<15> prev(pre);
            loop(ch, g) if(!prev[ch]) {
                int nxt = pre + (1 << ch); 
                int l = -1;
                int r = n-1;
                while(r - l >= 3) {
                    int m1 = l + (r-l)/3;
                    int m2 = r - (r-l)/3;
                    double a = cost(pre, ch, m1);
                    double b = cost(pre, ch, m2);
                    if(a < b)
                        r = m2;
                    else
                        l = m1;
                }
                for(int idx = l; idx <= r; idx++)
                    ckmin(dp[nxt], dp[pre] + cost(pre, ch, idx));
            }
        }
     
     
        cout << setprecision(16) << dp[(1 << g) - 1] << endl;
     
    }
     
    signed main() {
     
        fast_io;
     
        int t = 1; //cin >> t;
        while(t--)
            solve();
     
        return 0;
     
    }

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