oj.uz

Submission #654819

# Submission time Handle Problem Language Result Execution time Memory
654819 2022-11-01T17:33:13 Z Lobo Boarding Passes (BOI22_passes) C++17
60 / 100
 187 ms 193964 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];
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 >= 0; x--) {
                prepr[i][j][x] = prepr[i][j][x+1];
                if(pf[(1<<j)][x]-pf[(1<<j)][x-1]) prepr[i][j][x]+= pf[(1<<i)][n]-pf[(1<<i)][x];
                if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepr[i][j][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;
            // }
            if(ans != 0) {
                ans1+= pfl[i][pos[i][ans-1]];
                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()) {
            //     for(int j = 0; j < g; j++) {
            //         if(((1<<j)&mask1) == 0) continue;
            //         ans1+= prepr[i][j][pos[i][ans-1]+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:139:34: 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]
  139 |             for(int j = ans+1; j <= pos[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2252 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 2376 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2376 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 328 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1608 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 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 1352 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 1352 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 2 ms 1352 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 328 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1608 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 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 1352 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 1352 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 2 ms 1352 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 1604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 1620 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 1608 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 1608 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 992 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 1352 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 1 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 187 ms 193856 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 164 ms 193828 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 160 ms 193896 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 165 ms 193760 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 177 ms 193868 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 183 ms 193792 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 178 ms 193832 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 183 ms 193932 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 187 ms 193964 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 179 ms 193788 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2252 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 2376 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2376 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 328 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 1608 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 1620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 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 1352 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 1352 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 2 ms 1352 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 1604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 1620 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 1608 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 1608 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 992 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 2 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 1352 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 1 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 187 ms 193856 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 164 ms 193828 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 160 ms 193896 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 165 ms 193760 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 177 ms 193868 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 183 ms 193792 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 178 ms 193832 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 183 ms 193932 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 187 ms 193964 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 179 ms 193788 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 728 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Runtime error 40 ms 20336 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -