oj.uz

Submission #735794

# Submission time Handle Problem Language Result Execution time Memory
735794 2023-05-04T16:41:30 Z Victor Boarding Passes (BOI22_passes) C++17
5 / 100
 49 ms 25904 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

// 2^g state DP, what groups have boarded
// g transitions, next group to board
// to find optimal boarding side for next group we do not need to to O(N) thing
// instead we go through each group and find how many are to the left when doing binary search
// we precompute tables for each group
// something like O(2^g * g² * log n)

const ll g=15;
ll n;
string s;
double memo[1<<g];
vll groups_sum[g];
vll groups_pos[g];
vll groups_cross[g][g];

double dp(ll mask) {
    if(mask==(1<<g)-1) return 0;

    double &ans=memo[mask];
    if(ans!=-1) return ans;

    ans=1e10;
    rep(i,0,g) if(!(mask&(1<<i))) {
        
        ll group_size=sz(groups_pos[i]);
        ll lo=0,hi=group_size;

        while(lo!=hi) {
            ll mid=(lo+hi)/2;
            //cout<<"i = "<<i<<" mid = "<<mid<<endl;
            ll pos=groups_pos[i][mid];
            ll peopleL=0,peopleR=0;

            rep(j,0,g) if(mask&(1<<j)) {
                ll val=groups_sum[j][pos];
                peopleL+=val;
                peopleR+=group_size-val;
            }

            if(double(peopleL)+double(mid)/2.0<double(peopleR)+double(group_size-mid-1)/2.0) lo=mid+1;
            else hi=mid;
        }

        rep(k,max(0LL,lo-1),min(group_size+1,lo+2)) {
            double add=0;
            rep(j,0,g) if(mask&(1<<j)) add+=double(groups_cross[i][j][k]);

            ll peopleL=k,peopleR=(group_size)-peopleL;
            add+=double(peopleL*(peopleL-1))/4.0+double(peopleR*(peopleR-1))/4.0;
            
            //if(add==100800) cout<<"peopleL = "<<peopleL<<" peopleR = "<<peopleR<<endl;
            ans=min(ans,dp(mask|(1<<i))+add);
        }
    }

    //cout<<"mask = "<<mask<<" ans = "<<ans<<endl;
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i,0,1<<g) memo[i]=-1;
    cin>>s;

    n=sz(s);
    trav(chr,s) chr-='A';

    rep(i,0,g) groups_sum[i].assign(n+1,0);
    rep(i,0,n) {
        ++groups_sum[(ll)s[i]][i];
        groups_pos[(ll)s[i]].pb(i);
    }

    rep(i,0,g) rep(j,1,n) groups_sum[i][j]+=groups_sum[i][j-1];
    rep(i,0,g) rep(j,0,g) {
        ll val=0;
        groups_cross[i][j].pb(0);
        trav(pos,groups_pos[i]) {
            val+=groups_sum[j][pos];
            groups_cross[i][j].pb(val);
        }
        
        val=0;
        per(k,0,sz(groups_pos[i])) {
            ll pos=groups_pos[i][k];
            val+=sz(groups_pos[j])-groups_sum[j][pos];
            groups_cross[i][j][k]+=val;
        }
    }
    
    cout<<setprecision(20)<<dp(0)<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 13 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 13 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 16 ms 840 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 41 ms 20720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 48 ms 24472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 49 ms 25876 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 47 ms 25904 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 14 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 30 ms 620 KB 1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 14 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 30 ms 620 KB 1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 13 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 13 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 16 ms 840 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 41 ms 20720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 48 ms 24472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 49 ms 25876 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 47 ms 25904 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 15 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 14 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 30 ms 620 KB 1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612'
13 Halted 0 ms 0 KB -