oj.uz

답안 #654601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654601 2022-10-31T20:59:24 Z Lobo Boarding Passes (BOI22_passes) C++17
55 / 100
 199 ms 160972 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();
    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);
            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:55: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]
   55 |             for(int j = 1; j <= pos[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 2 ms 724 KB 1st numbers differ - expected: '772893586.0000000000', found: '0.0000000000', error = '1.0000000000'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 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 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 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 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 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 192 ms 160768 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 145 ms 160760 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 146 ms 160972 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 150 ms 160736 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 180 ms 160872 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 176 ms 160844 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 179 ms 160792 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 175 ms 160804 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 183 ms 160816 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 199 ms 160876 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 2 ms 724 KB 1st numbers differ - expected: '772893586.0000000000', found: '0.0000000000', error = '1.0000000000'
7 Halted 0 ms 0 KB -