Submission #748677

#	Time	Username	Problem	Language	Result	Execution time	Memory
748677		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 >= 4) {
                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