oj.uz

Submission #723283

# Submission time Handle Problem Language Result Execution time Memory
723283 2023-04-13T13:51:42 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 1350 ms 379088 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;
 
#define int ll
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
signed 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, (int)0); j < min((int)ix[i].size(), 2 + max((int)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 89 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 46 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 270 ms 297952 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 297 ms 355788 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 333 ms 378980 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 322 ms 378908 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 158 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 150 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 80 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 63 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 197 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 108 ms 672 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 98 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 106 ms 716 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 112 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 117 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 97 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 106 ms 676 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 69 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 71 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 158 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 150 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 80 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 63 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 197 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 108 ms 672 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 98 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 106 ms 716 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 112 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 117 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 97 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 106 ms 676 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 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 74 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 157 ms 956 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 91 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 62 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 162 ms 900 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 108 ms 672 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 109 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 94 ms 684 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 106 ms 668 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 109 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 113 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 98 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 102 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 105 ms 720 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 109 ms 38380 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 105 ms 38368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 456 ms 38312 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 366 ms 38268 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 299 ms 38380 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 388 ms 38220 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 402 ms 37520 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 667 ms 37508 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 810 ms 37512 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 489 ms 37496 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 508 ms 37504 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 634 ms 37500 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 46 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 79 ms 4336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 270 ms 297952 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 297 ms 355788 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 333 ms 378980 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 322 ms 378908 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 69 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 71 ms 960 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 158 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 150 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 80 ms 952 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 63 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 197 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 108 ms 672 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 98 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 106 ms 716 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 112 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 117 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 97 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 106 ms 676 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 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 74 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 157 ms 956 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 91 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 62 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 162 ms 900 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 108 ms 672 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 109 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 94 ms 684 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 106 ms 668 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 109 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 113 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 98 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 102 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 105 ms 720 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 109 ms 38380 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 105 ms 38368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 456 ms 38312 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 366 ms 38268 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 299 ms 38380 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 388 ms 38220 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 402 ms 37520 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 667 ms 37508 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 810 ms 37512 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 489 ms 37496 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 508 ms 37504 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 634 ms 37500 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 73 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 92 ms 676 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 78 ms 3976 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 49 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 60 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 80 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 284 ms 298168 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 318 ms 355752 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 333 ms 378948 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 346 ms 379088 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 57 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 71 ms 948 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 159 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 78 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 62 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 163 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 100 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 115 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 108 ms 672 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 94 ms 668 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 105 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 107 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 111 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 100 ms 692 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 124 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 102 ms 676 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 106 ms 38376 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 108 ms 38360 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 484 ms 38228 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 277 ms 38356 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 395 ms 38112 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 436 ms 37580 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 675 ms 37460 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 839 ms 37520 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 504 ms 37612 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 480 ms 37580 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 666 ms 37496 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Incorrect 1350 ms 378188 KB 1st numbers differ - expected: '1239972790.0000000000', found: '1249975000.0000000000', error = '0.0080664754'
97 Halted 0 ms 0 KB -