제출 #767606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767606		raysh07	Boarding Passes (BOI22_passes)	C++17	100 / 100	355 ms	26624 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, k;
const int K = 16;
const int N = 1e5 + 69;
int dp[1 << K]; //store 2 * value 
int F[N][K]; //fenwick for all positions 
vector <int> pos[K];
int add[K][K][N]; //value to add if i was already there, j is newly added, and we add it by prefix of size k, and rest suffix 

void upd(int x, int j){
    for (int i = x; i <= n; i += i & (-i)) F[i][j]++;
}

int query(int x, int j){
    int res = 0;
    for (int i = x; i; i -= i & (-i)) res += F[i][j];
    return res;
}

void pre(){
    for (int i = 0; i < k; i++){
        for (int j = 0; j < k; j++){
            if (i == j) continue;
            
            int sz = pos[j].size();
            int curr = 0;
            for (int pref = 1; pref <= sz; pref++){
                curr += query(pos[j][pref - 1], i);
                add[i][j][pref] = curr;
            }
            curr = 0;
            for (int pref = sz - 1; pref >= 0; pref--){
                curr += query(n, i) - query(pos[j][pref], i);
                add[i][j][pref] += curr;
            }
        }
    }
}

int f(int pref, int mask, int i){
    int ans = 0;
    int tot = pos[i].size();
    
    ans += pref * (pref - 1) / 2;
    ans += (tot - pref) * (tot - pref - 1) / 2;
    
    // if (i == 0){
    //     cout << pref << " " << ans << "\n";
    // }
    
    for (int j = 0; j < k; j++){
        if (mask >> j & 1){
            ans += 2 * add[j][i][pref];
        }
    }
    
    return ans;
}

int transition(int mask, int i){
    int l = 0, r = pos[i].size();
    
    while (r - l > 2){
        int m1 = (2 * l + r) / 3;
        int m2 = (l + 2 * r) / 3;
        
        int x1 = f(m1, mask, i);
        int x2 = f(m2, mask, i);
        
        if (x1 > x2) l = m1;
        else r = m2;
    }
    
    int ans = INF;
    
    for (int j = l; j <= r; j++) ans = min(ans, f(j, mask, i));
    
    // cout << mask << " " << i << " " << ans << " " << dp[mask] << "\n";
    
    return dp[mask] + ans;
}

void Solve() 
{
    string s; cin >> s;
    n = s.length();
    k = 15;
    for (int i = 0; i < n; i++){
        pos[s[i] - 'A'].push_back(i + 1);
        upd(i + 1, s[i] - 'A');
    }
    
    pre();
    
    for (int i = 1; i < (1 << k); i++) dp[i] = INF;
    
    for (int i = 1; i < (1 << k); i++){
        for (int j = 0; j < k; j++){
            if (i >> j & 1){
                dp[i] = min(dp[i], transition(i ^ (1 << j), j));
            }
        }
    }
    
    int ans = dp[(1 << k) - 1];
    if (ans & 1) cout << (ans/2) << ".5\n";
    else cout << (ans/2) << "\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;
}

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