oj.uz

Submission #723293

# Submission time Handle Problem Language Result Execution time Memory
723293 2023-04-13T13:56:03 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1545 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];
                        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

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3960 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 41 ms 552 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 54 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 82 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 280 ms 297328 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 342 ms 354960 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 340 ms 378124 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 357 ms 378144 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 66 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 167 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 145 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 73 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 64 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 156 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 106 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 96 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 104 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 93 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 107 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 121 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 114 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 101 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 66 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 167 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 145 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 73 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 64 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 156 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 106 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 96 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 104 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 93 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 107 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 121 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 114 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 101 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 61 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 65 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 170 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 155 ms 952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 76 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 63 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 178 ms 892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 118 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 103 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 125 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 123 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 112 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 129 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 124 ms 688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 101 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 111 ms 684 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 106 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 142 ms 38288 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 114 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 582 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 417 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 311 ms 38288 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 446 ms 38100 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 434 ms 37472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 739 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 911 ms 37464 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 582 ms 37476 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 602 ms 37468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 676 ms 37464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3960 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 41 ms 552 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 54 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 82 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 280 ms 297328 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 342 ms 354960 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 340 ms 378124 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 357 ms 378144 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 52 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 66 ms 952 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 167 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 145 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 73 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 64 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 156 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 106 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 96 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 104 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 93 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 107 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 121 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 114 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 95 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 101 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 104 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 61 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 65 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 170 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 155 ms 952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 76 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 63 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 178 ms 892 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 118 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 103 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 125 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 123 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 112 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 129 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 124 ms 688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 101 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 111 ms 684 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 106 ms 684 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 142 ms 38288 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 114 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 582 ms 38248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 417 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 311 ms 38288 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 446 ms 38100 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 434 ms 37472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 739 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 911 ms 37464 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 582 ms 37476 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 602 ms 37468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 676 ms 37464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 77 ms 620 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 101 ms 688 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 78 ms 3956 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 40 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 49 ms 552 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 88 ms 4332 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 321 ms 297332 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 312 ms 354912 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 347 ms 378140 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 336 ms 378144 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 62 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 180 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 157 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 85 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 62 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 165 ms 888 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 103 ms 684 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 112 ms 676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 115 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 93 ms 684 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 118 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 129 ms 684 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 128 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 109 ms 684 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 125 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 120 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 109 ms 38228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 118 ms 38280 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 545 ms 38256 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 395 ms 38244 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 285 ms 38304 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 472 ms 38088 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 456 ms 37476 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 834 ms 37452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 848 ms 37460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 587 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 559 ms 37464 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 709 ms 37464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1545 ms 377748 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -