oj.uz

Submission #654600

# Submission time Handle Problem Language Result Execution time Memory
654600 2022-10-31T20:54:56 Z Lobo Boarding Passes (BOI22_passes) C++17
55 / 100
 209 ms 160912 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 maxn = 1e4+10;
const int maxg = 11;

int n, a[maxn];
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();

    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);
            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:47:30: 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]
   47 |             for(int j = 1; j <= pos[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~

Subtask #1
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 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 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 Incorrect 2 ms 724 KB 1st numbers differ - expected: '772893586.0000000000', found: '12522510.0000000000', error = '0.9837978860'
7 Halted 0 ms 0 KB -

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 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 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 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 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 980 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 980 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 852 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 852 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 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 198 ms 160832 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 156 ms 160776 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 152 ms 160912 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 176 ms 160756 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 183 ms 160904 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 182 ms 160828 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 206 ms 160844 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 187 ms 160796 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 209 ms 160888 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 190 ms 160892 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 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 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 Incorrect 2 ms 724 KB 1st numbers differ - expected: '772893586.0000000000', found: '12522510.0000000000', error = '0.9837978860'
7 Halted 0 ms 0 KB -