oj.uz

답안 #723294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723294 2023-04-13T13:56:13 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1177 ms 378044 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    char a = 'A';
    string s; cin >> s;
    const int G = 15;
    int n = s.size();
    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    vector suml(G, vector(G, vector(n, 0ll)));
    vector sumr(G, vector(G, vector(n, 0ll)));
    vector cl(G, vector(n, 0ll));
    vector cr(G, vector(n, 0ll));
    vector ix(G, vector<int>());
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                suml[c1][c2][i] = res;
            }
        }
    }
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = n-1; i >= 0; i --) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                sumr[c1][c2][i] = res;
            }
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = 0; i < n;i ++) {
            if (s[i] == j+a)
                c++;
            cl[j][i] = c;
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == j+a)
                c++;
            cr[j][i] = c;
        }
    }
    for (int i = 0; i < n ;i++) 
        ix[s[i] - a].push_back(i);

    vector memo(1<<G, (ll)1e18);
    memo[(1<<G)-1] = 0;
    for (int used = (1<<G)-1-1; used >= 0; used--) {
        ll& res = memo[used];
        for (int i = 0 ;i < G; i++) {
            if (used&1<<i) continue;

            auto f = [&](int j) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++) {
                    if (used&1<<c2) {
                        if (j) sum += suml[i][c2][j-1];
                        if (j <n-1)sum += sumr[i][c2][j];
                    }
                }
                return sum * 4 + (j < n-1 ? exp_inv(cr[i][j]) : 0) + (j ? exp_inv(cl[i][j-1]) : 0);
            };

            int l = -1, r = (int)ix[i].size()-2;
            while (l < r-1) {
                int m = (l+r) / 2;
                ll a = f(ix[i][m]), b = f(ix[i][m+1]);
                if (a == b) break;
                else if (a < b) r = m;
                else l = m;
            }
 
            for (int j = max(l, 0); j < min((int)ix[i].size(), 2 + max(0, r)); j++) {
                res = min(res, f(ix[i][j]) + memo[used |1<<i]);
            }
            res = min(res, f(0) + memo[used | 1<<i]);
            res = min(res, f(n) + memo[used | 1<<i]);
        }
    };
    ll ans;
    if (n > 10000) ans = exp_inv(n / 2) + exp_inv(n - n / 2);
    else ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
    cout << endl;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 3928 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 46 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4324 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 317 ms 297252 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 337 ms 354868 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 356 ms 377980 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 348 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 164 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 149 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 86 ms 960 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 165 ms 892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 94 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 101 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 114 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 96 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 100 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 133 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 127 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 684 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 107 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 101 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 164 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 149 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 86 ms 960 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 165 ms 892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 94 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 101 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 114 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 96 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 100 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 133 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 127 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 684 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 107 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 101 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 68 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 168 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 143 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 72 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 58 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 173 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 113 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 104 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 113 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 104 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 119 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 127 ms 720 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 114 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 91 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 103 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 99 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 101 ms 38280 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 109 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 537 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 455 ms 38252 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 326 ms 38284 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 499 ms 38080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 482 ms 37448 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 894 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 980 ms 37448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 597 ms 37444 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 521 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 728 ms 37456 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 3928 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 46 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4324 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 317 ms 297252 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 337 ms 354868 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 356 ms 377980 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 348 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 63 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 71 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 164 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 149 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 86 ms 960 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 61 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 165 ms 892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 94 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 101 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 114 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 96 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 100 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 133 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 127 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 95 ms 684 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 107 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 101 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 68 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 168 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 143 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 72 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 58 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 173 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 113 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 104 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 113 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 104 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 119 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 127 ms 720 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 114 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 91 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 103 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 99 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 101 ms 38280 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 109 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 537 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 455 ms 38252 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 326 ms 38284 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 499 ms 38080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 482 ms 37448 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 894 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 980 ms 37448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 597 ms 37444 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 521 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 728 ms 37456 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 76 ms 624 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 93 ms 680 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 77 ms 3956 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 40 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 50 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 77 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 275 ms 297284 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 316 ms 354768 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 368 ms 378036 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 325 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 53 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 64 ms 940 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 160 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 191 ms 972 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 80 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 60 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 166 ms 900 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 102 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 105 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 106 ms 672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 91 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 116 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 100 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 123 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 101 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 115 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 101 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 103 ms 38228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 104 ms 38264 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 473 ms 38244 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 365 ms 38344 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 268 ms 38272 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 387 ms 38080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 418 ms 37464 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 658 ms 37464 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 777 ms 37448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 492 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 485 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 621 ms 37456 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1177 ms 377648 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -