oj.uz

Submission #723298

# Submission time Handle Problem Language Result Execution time Memory
723298 2023-04-13T13:57:21 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1239 ms 378192 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-1, 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

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 48 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 266 ms 297200 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 325 ms 354852 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 311 ms 378192 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 331 ms 378084 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 64 ms 940 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 171 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 164 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 75 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 59 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 168 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 99 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 113 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 123 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 124 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 132 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 114 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 131 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 115 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 112 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 64 ms 940 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 171 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 164 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 75 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 59 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 168 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 99 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 113 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 123 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 124 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 132 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 114 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 131 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 115 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 112 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 62 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 74 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 180 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 167 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 88 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 63 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 196 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 118 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 124 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 117 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 106 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 122 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 127 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 116 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 101 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 128 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 115 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 106 ms 38276 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 112 ms 38264 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 501 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 390 ms 38236 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 283 ms 38280 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 420 ms 38084 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 433 ms 37460 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 733 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 865 ms 37448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 521 ms 37448 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 561 ms 37452 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 665 ms 37460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 48 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 266 ms 297200 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 325 ms 354852 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 311 ms 378192 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 331 ms 378084 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 56 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 64 ms 940 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 171 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 164 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 75 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 59 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 168 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 99 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 113 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 123 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 124 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 132 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 114 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 131 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 115 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 112 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 62 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 74 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 180 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 167 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 88 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 63 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 196 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 118 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 124 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 117 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 106 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 122 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 127 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 116 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 101 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 128 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 115 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 106 ms 38276 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 112 ms 38264 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 501 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 390 ms 38236 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 283 ms 38280 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 420 ms 38084 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 433 ms 37460 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 733 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 865 ms 37448 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 521 ms 37448 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 561 ms 37452 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 665 ms 37460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 67 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 91 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 74 ms 3948 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 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 48 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 74 ms 4324 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 262 ms 297200 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 296 ms 354948 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 311 ms 378084 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 319 ms 378148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 50 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 64 ms 972 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 171 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 156 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 75 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 58 ms 608 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 168 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 100 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 107 ms 684 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 122 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 97 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 106 ms 668 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 105 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 112 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 93 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 103 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 99 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 105 ms 38280 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 108 ms 38272 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 533 ms 38240 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 376 ms 38228 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 268 ms 38228 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 413 ms 38100 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 445 ms 37580 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 702 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 915 ms 37460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 518 ms 37452 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 531 ms 37452 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 666 ms 37448 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1239 ms 377652 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -