oj.uz

Submission #723280

# Submission time Handle Problem Language Result Execution time Memory
723280 2023-04-13T13:47:10 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1180 ms 378144 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];
                        sum += sumr[i][c2][j];
                    }
                }
                return sum * 4 + exp_inv(cr[i][j]) + (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-1) + 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 83 ms 3960 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 47 ms 596 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 81 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 314 ms 297248 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 342 ms 354872 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 325 ms 378020 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 339 ms 378032 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 161 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 148 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 84 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 62 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 166 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 99 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 116 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 109 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 99 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 103 ms 684 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 121 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 115 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 104 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 101 ms 680 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 99 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 161 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 148 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 84 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 62 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 166 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 99 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 116 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 109 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 99 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 103 ms 684 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 121 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 115 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 104 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 101 ms 680 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 99 ms 596 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 70 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 165 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 151 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 81 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 70 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 164 ms 816 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 99 ms 684 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 120 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 103 ms 692 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 101 ms 680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 106 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 124 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 102 ms 680 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 101 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 103 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 122 ms 38292 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 111 ms 38248 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 461 ms 38376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 369 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 281 ms 38296 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 392 ms 38112 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 406 ms 37472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 655 ms 37472 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 764 ms 37464 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 481 ms 37580 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 476 ms 37464 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 598 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 83 ms 3960 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 47 ms 596 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 81 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 314 ms 297248 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 342 ms 354872 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 325 ms 378020 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 339 ms 378032 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 62 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 71 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 161 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 148 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 84 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 62 ms 612 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 166 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 99 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 116 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 109 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 99 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 103 ms 684 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 121 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 115 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 104 ms 720 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 101 ms 680 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 99 ms 596 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 70 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 165 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 151 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 81 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 70 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 164 ms 816 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 99 ms 684 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 120 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 103 ms 692 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 101 ms 680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 106 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 124 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 102 ms 680 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 101 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 103 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 122 ms 38292 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 111 ms 38248 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 461 ms 38376 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 369 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 281 ms 38296 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 392 ms 38112 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 406 ms 37472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 655 ms 37472 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 764 ms 37464 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 481 ms 37580 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 476 ms 37464 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 598 ms 37460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 73 ms 632 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 107 ms 680 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 90 ms 3952 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 50 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 55 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 78 ms 4336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 300 ms 297284 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 298 ms 354972 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 355 ms 378132 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 310 ms 378144 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 58 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 71 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 161 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 146 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 84 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 67 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 163 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 108 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 112 ms 684 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 107 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 94 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 110 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 116 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 111 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 101 ms 676 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 105 ms 680 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 111 ms 680 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 110 ms 38276 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 481 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 388 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 283 ms 38292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 415 ms 38092 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 401 ms 37476 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 704 ms 37584 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 798 ms 37460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 500 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 506 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 627 ms 37460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1180 ms 377748 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -