oj.uz

Submission #654797

# Submission time Handle Problem Language Result Execution time Memory
654797 2022-11-01T16:21:18 Z Lobo Boarding Passes (BOI22_passes) C++17
60 / 100
 239 ms 192460 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];
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<<j)][x]-pf[(1<<j)][x-1]) prepl[i][j][x]+= pf[(1<<i)][x];
                if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepl[i][j][x]+= ((dbl) 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) {
            //     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:134: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]
  134 |             for(int j = ans+1; j <= pos[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~~

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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 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 5 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1620 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 1236 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 2 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1620 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 1236 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 2 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 1620 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 1620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 1236 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 1492 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 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 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 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 212 ms 192232 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 198 ms 192160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 178 ms 192376 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 175 ms 192200 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 202 ms 192220 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 239 ms 192460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 199 ms 192252 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 199 ms 192264 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 215 ms 192240 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 201 ms 192248 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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 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 5 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 1620 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 1236 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 2 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 1620 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 1620 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 1620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 1236 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 1492 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 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 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 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 212 ms 192232 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 198 ms 192160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 178 ms 192376 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 175 ms 192200 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 202 ms 192220 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 239 ms 192460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 199 ms 192252 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 199 ms 192264 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 215 ms 192240 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 201 ms 192248 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Runtime error 37 ms 20308 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -