oj.uz

Submission #654792

# Submission time Handle Problem Language Result Execution time Memory
654792 2022-11-01T15:54:46 Z Lobo Boarding Passes (BOI22_passes) C++17
60 / 100
 192 ms 160956 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)];
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]++;
        }

        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;
            }
            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:101: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]
  101 |             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 336 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 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 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2256 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2256 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 332 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 976 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 976 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 972 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 564 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 844 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 332 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 976 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 976 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 972 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 564 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 844 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 972 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 964 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 844 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 844 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 852 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 592 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 181 ms 160824 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 143 ms 160840 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 147 ms 160956 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 151 ms 160808 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 192 ms 160852 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 166 ms 160828 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 173 ms 160900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 167 ms 160856 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 172 ms 160784 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 171 ms 160884 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 336 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 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 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2256 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2256 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 332 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 976 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 976 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 972 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 564 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 844 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 852 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 972 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 964 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 844 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 844 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 852 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 592 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 181 ms 160824 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 143 ms 160840 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 147 ms 160956 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 151 ms 160808 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 192 ms 160852 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 166 ms 160828 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 173 ms 160900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 167 ms 160856 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 172 ms 160784 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 171 ms 160884 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 460 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Runtime error 41 ms 20464 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -