Submission #723301

# Submission time Handle Problem Language Result Execution time Memory
723301 2023-04-13T13:59:30 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
1141 ms 378152 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 ? 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;
}

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3924 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 37 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 49 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 77 ms 4344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 252 ms 297252 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 288 ms 354784 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 311 ms 378152 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 302 ms 378036 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
# Verdict Execution time Memory Grader output
1 Correct 50 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 70 ms 972 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 167 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 144 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 852 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 166 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 122 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 99 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 108 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 97 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 108 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 107 ms 672 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 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 114 ms 676 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'
# Verdict Execution time Memory Grader output
1 Correct 50 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 70 ms 972 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 167 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 144 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 852 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 166 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 122 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 99 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 108 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 97 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 108 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 107 ms 672 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 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 114 ms 676 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 58 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 70 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 177 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 149 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 76 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 57 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 166 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 101 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 115 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 108 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 94 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 101 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 102 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 109 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 90 ms 676 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 103 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 96 ms 676 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 98 ms 38280 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 99 ms 38268 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 456 ms 38240 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 366 ms 38232 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 265 ms 38280 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 393 ms 38080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 398 ms 37464 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 709 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 856 ms 37452 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 523 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 539 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 670 ms 37580 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
# Verdict Execution time Memory Grader output
1 Correct 76 ms 3924 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 37 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 49 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 77 ms 4344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 252 ms 297252 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 288 ms 354784 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 311 ms 378152 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 302 ms 378036 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 50 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 70 ms 972 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 167 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 144 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 74 ms 852 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 166 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 122 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 99 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 108 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 97 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 108 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 107 ms 672 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 102 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 114 ms 676 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 58 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 70 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 177 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 149 ms 936 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 76 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 57 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 166 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 101 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 115 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 108 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 94 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 101 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 102 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 109 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 90 ms 676 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 103 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 96 ms 676 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 98 ms 38280 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 99 ms 38268 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 456 ms 38240 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 366 ms 38232 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 265 ms 38280 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 393 ms 38080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 398 ms 37464 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 709 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 856 ms 37452 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 523 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 539 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 670 ms 37580 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 68 ms 612 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 84 ms 684 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 71 ms 3924 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 39 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 46 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 71 ms 4324 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 256 ms 297168 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 291 ms 354788 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 310 ms 378032 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 381 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 51 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 62 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 164 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 144 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 73 ms 940 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 58 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 161 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 97 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 101 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 105 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 91 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 104 ms 668 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 101 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 110 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 90 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 101 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 97 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 100 ms 38228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 99 ms 38268 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 453 ms 38340 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 358 ms 38232 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 258 ms 38272 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 401 ms 38216 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 397 ms 37528 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 642 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 803 ms 37460 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 488 ms 37460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 494 ms 37460 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 620 ms 37460 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1141 ms 377648 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -