oj.uz

Submission #735793

# Submission time Handle Problem Language Result Execution time Memory
735793 2023-05-04T16:40:00 Z Victor Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 20812 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,0,group_size+1) {
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 844 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 11 ms 596 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 588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 326 ms 820 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2063 ms 20812 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 38 ms 600 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 43 ms 608 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 44 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 42 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 16 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 41 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 20 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 25 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 584 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 21 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 38 ms 600 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 43 ms 608 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 44 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 42 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 16 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 41 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 20 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 25 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 584 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 21 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 17 ms 592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 39 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 42 ms 608 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 52 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 40 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 16 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 37 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 21 ms 608 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 21 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 22 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 24 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 21 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 21 ms 588 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 20 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 21 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 20 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 20 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2074 ms 3156 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 844 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 11 ms 596 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 588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 326 ms 820 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2063 ms 20812 KB Time limit exceeded
7 Halted 0 ms 0 KB -