oj.uz

Submission #654822

# Submission time Handle Problem Language Result Execution time Memory
654822 2022-11-01T17:41:50 Z Lobo Boarding Passes (BOI22_passes) C++17
60 / 100
 183 ms 195456 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn1 = 1e5+10;
const int maxn = 1e4+10;
const int maxg = 11;

int n, a[maxn1];
dbl pf[(1<<maxg)][maxn], dp[(1<<maxg)], prepl[maxg][maxg][maxn], prepr[maxg][maxg][maxn], pfl[maxg][maxn], sfr[maxg][maxn];
vector<int> pos[maxg];

void solve() {
    string s; cin >> s;
    n = s.size();
    vector<char> cc;
    for(auto x : s) cc.pb(x);
    sort(all(cc));
    cc.erase(unique(all(cc)),cc.end());
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(all(cc),s[i-1])-cc.begin();
        pos[a[i]].pb(i);
    }
    int g = cc.size();
    if(g == 1) {
        dbl ans = 0;
        for(int i = 1; i <= n; i++) ans+= min((dbl) (i-1)/2,(dbl) (n-i)/2);
        cout.setf(ios::fixed);
        cout.precision(10);
        cout << ans << endl;
        return;
    }

    for(int mask = 1; mask < (1<<g); mask++) {
        pf[mask][0] = 0;
        for(int i = 1; i <= n; i++) {
            pf[mask][i] = pf[mask][i-1];
            if((1<<a[i])&mask) pf[mask][i]++;
        }
    }

    for(int i = 0; i < g; i++) {
        for(int j = 0; j < g; j++) {
            for(int x = 1; x <= n; x++) {
                prepl[i][j][x] = prepl[i][j][x-1];
                if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepl[i][j][x]+= pf[(1<<j)][x-1];
            }
        }

        for(int x = 1; x <= n; x++) {
            pfl[i][x] = pfl[i][x-1];
            if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) pfl[i][x]+= ((dbl) pf[(1<<i)][x-1])/2;
        }
    }

    for(int i = 0; i < g; i++) {
        for(int j = 0; j < g; j++) {
            for(int x = n; x >= 1; x--) {
                prepr[i][j][x] = prepr[i][j][x+1];
                if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepr[i][j][x]+= pf[(1<<j)][n]-pf[(1<<j)][x];
            }
        }
        for(int x = n; x >= 1; x--) {
            sfr[i][x] = sfr[i][x+1];
            if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) sfr[i][x]+= ((dbl) pf[(1<<i)][n]-pf[(1<<i)][x])/2;
        }
    }

    for(int mask = 1; mask < (1<<g); mask++) {

        dp[mask] = inf;
        for(int i = 0; i < g; i++) {
            if(((1<<i)&mask) == 0) continue;
            int mask1 = mask-(1<<i);

            int l = 1;
            int r = pos[i].size();
            int ans = 0;
            // I want to find the greatest i such that I going to 
            // the left if better than i going to the right
            while(l <= r) {
                int mid = (l+r)/2;

                int x = pos[i][mid-1];
                // dbl ansl = pf[mask1][x]+((dbl) j-1)/2;
                dbl ansl = ((dbl) mid-1)/2; 
                for(int j = 0; j < g; j++) {
                    if(((1<<j)&mask1) == 0) continue;
                    ansl+= pf[(1<<j)][x];
                }

                // dbl ansr = pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2;
                dbl ansr = ((dbl) pos[i].size()-mid)/2; 
                for(int j = 0; j < g; j++) {
                    if(((1<<j)&mask1) == 0) continue;
                    ansr+= pf[(1<<j)][n]-pf[(1<<j)][x];
                }

                if(ansl <= ansr) {
                    ans = mid;
                    l = mid+1;
                }
                else {
                    r = mid-1;
                }
            }

            dbl ans1 = dp[mask1];
            // for(int j = 0; j < g; j++) {
            //     if(((1<<j)&mask1) == 0) continue;
            //     ans1+= prepc[i][j][x];
            // }

            int sz = pos[i].size();
            // for(int j = 1; j <= ans; j++) {
            //     int x = pos[i][j-1];
            //     ans1+= pf[mask1][x]+((dbl) j-1)/2;
            //     // cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
            // }
            int x = 0;
            if(ans != 0) x = pos[i][ans-1];
            if(ans != 0) {
                ans1+= pfl[i][x];
                for(int j = 0; j < g; j++) {
                    if(((1<<j)&mask1) == 0) continue;
                    ans1+= prepl[i][j][pos[i][ans-1]];
                }
            }
            if(ans != pos[i].size()) {
                ans1+= sfr[i][x+1];
                for(int j = 0; j < g; j++) {
                    if(((1<<j)&mask1) == 0) continue;
                    ans1+= prepr[i][j][x+1];
                }
            }
            // for(int j = ans+1; j <= pos[i].size(); j++) {
            //     int x = pos[i][j-1];
            //     ans1+= pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2;
            //     // cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
            // }
            dp[mask] = min(dp[mask],ans1);

        }



        // dp[mask] = inf;
        // for(int i = 0; i < g; i++) {
        //     if(((1<<i)&mask) == 0) continue;
        //     int mask1 = mask-(1<<i);
        //     dbl ans1 = dp[mask1];
        //     int sz = pos[i].size();
        //     for(int j = 1; j <= pos[i].size(); j++) {
        //         int x = pos[i][j-1];
        //         ans1+= min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2);
        //         // cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
        //     }
        //     dp[mask] = min(dp[mask],ans1);
        //     // cout << mask << " " << i << " = " << ans1 << " " << pf[mask1][1] << endl;
        // }
    }
    cout.setf(ios::fixed);
    cout.precision(10);
    cout << dp[(1<<g)-1] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

passes.cpp: In function 'void solve()':
passes.cpp:138:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             if(ans != pos[i].size()) {
      |                ~~~~^~~~~~~~~~~~~~~~
passes.cpp:123:17: warning: unused variable 'sz' [-Wunused-variable]
  123 |             int sz = pos[i].size();
      |                 ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2124 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2252 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 2252 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1620 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1620 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 1748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 1748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 1748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 1620 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 596 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 167 ms 195376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 183 ms 195388 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 157 ms 195440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 157 ms 195384 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 155 ms 195276 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 164 ms 195308 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 157 ms 195272 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 164 ms 195456 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 162 ms 195348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 179 ms 195280 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2124 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2252 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 2252 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 1748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 1748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 1748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 2 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 1620 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 1748 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 1748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 1748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 1620 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 2 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 2 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 2 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 596 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 167 ms 195376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 183 ms 195388 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 157 ms 195440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 157 ms 195384 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 155 ms 195276 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 164 ms 195308 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 157 ms 195272 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 164 ms 195456 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 162 ms 195348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 179 ms 195280 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 724 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Runtime error 39 ms 20400 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -