oj.uz

Submission #594020

# Submission time Handle Problem Language Result Execution time Memory
594020 2022-07-11T22:30:50 Z MohammadAghil Boarding Passes (BOI22_passes) C++17
0 / 100
 12 ms 724 KB 
#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
//   #pragma GCC optimization ("unroll-loops")
//  #pragma GCC optimization ("O3")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
  #define rep(i,l,r) for(int i = (l); i < (r); i++)
     #define all(x) begin(x), end(x)
        #define sz(x) (int)(x).size()
            #define pb push_back
                #define ss second
                     #define ff first
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = ll(1e9) + 7, maxn = 1e5 + 5, maxg = 15, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int a[maxn], lst[maxg], cnt[maxg];
vector<int> pos[maxg];
ll cnt_prf[maxn][maxg], cnt_suf[maxn][maxg];
ll dp[1<<maxg];

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    string s; cin >> s;
    int n = sz(s);
    rep(i,0,n) a[i] = s[i]-'A', pos[a[i]].pb(i);
    
    rep(i,0,maxg) lst[i] = -1;
    rep(i,0,n){
        rep(j,0,maxg){
            cnt_prf[i][j] = (lst[a[i]] == -1? 0: cnt_prf[lst[a[i]]][j]) + cnt[j];
        }
        lst[a[i]] = i, cnt[a[i]]++;
    }
    rep(i,0,maxg) lst[i] = n, cnt[i] = 0;
    per(i,n-1,0){
        rep(j,0,maxg){
            cnt_suf[i][j] = (lst[a[i]] == n? 0: cnt_suf[lst[a[i]]][j]) + cnt[j];
        }
        lst[a[i]] = i, cnt[a[i]]++;
    }
    
    rep(i,0,n) rep(j,0,maxg) cnt_prf[i][j] <<= 1ll, cnt_suf[i][j] <<= 1ll;
    
    rep(msk,1,1<<maxg){
        vector<int> bt;
        rep(j,0,maxg) if(msk>>j&1) bt.pb(j);
        dp[msk] = inf;
        for(int c: bt){
            if(cnt[c] == 0){
                dp[msk] = dp[msk^(1<<c)];
                break;
            }
            
            auto calc = [&](ll x){
                ll res = x*(x-1)/2ll + (cnt[c]-x)*(cnt[c]-x-1)/2ll;
                for(int r: bt) if(r - c){
                    if(x > 0 && x <= cnt[c]) res += cnt_prf[pos[c][x-1]][r];
                    if(x < cnt[c] && x >= 0) res += cnt_suf[pos[c][x]][r];
                }
                return res;
            };
            
            int lx = 0, rx = cnt[c]+1;
            while(lx + 1 < rx){
                int mid = (lx + rx)>>1;
                ll l = calc(mid), r = calc(mid+1);
                if(l >= r) lx = mid+1;
                else rx = mid;
            }
            
            dp[msk] = min(dp[msk], dp[msk^(1<<c)] + min(calc(lx), calc(rx)));
        }
    }
    
    cout << fixed << setprecision(1) << 1.*dp[(1<<maxg)-1]/2. << endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Incorrect 8 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Incorrect 8 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -