oj.uz

Submission #723269

# Submission time Handle Problem Language Result Execution time Memory
723269 2023-04-13T13:25:09 Z drdilyor Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 378044 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
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);
    for (int i = 0; i < G; i++)
        ix[i].push_back(n-1);

    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;
                int 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 = (l == -1 || l >= (int)ix[i].size()) ? 0 : ix[i][l];
                 j <= (r >= 0 ? ix[i][r]+1 : 0) && j < n; j++) {
                res = min(res, f(j) + memo[used |1<<i]);
            }
            for (int j = max(l, 0); j <= clamp(r+1, 0, (int)ix[i].size()-1); j++)
                res = min(res, f(ix[i][j]) + 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";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 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 26 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 28 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 40 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 215 ms 297192 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 286 ms 354876 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 260 ms 378000 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 284 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 35 ms 968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 116 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 140 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 55 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 49 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 99 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 81 ms 668 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 89 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 92 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 77 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 82 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 85 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 94 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 76 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 85 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 81 ms 700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 35 ms 968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 116 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 140 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 55 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 49 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 99 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 81 ms 668 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 89 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 92 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 77 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 82 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 85 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 94 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 76 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 85 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 81 ms 700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 37 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 36 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 107 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 130 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 61 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 52 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 100 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 81 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 85 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 87 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 77 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 84 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 83 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 91 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 75 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 88 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 76 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 72 ms 38228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 63 ms 38228 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 326 ms 38236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Execution timed out 2068 ms 38204 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 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 26 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 28 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 40 ms 4328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 215 ms 297192 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 286 ms 354876 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 260 ms 378000 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 284 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 35 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 35 ms 968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 116 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 140 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 55 ms 944 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 49 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 99 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 81 ms 668 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 89 ms 680 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 92 ms 668 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 77 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 82 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 85 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 94 ms 676 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 76 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 85 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 81 ms 700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 37 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 36 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 107 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 130 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 61 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 52 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 100 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 81 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 85 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 87 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 77 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 84 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 83 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 91 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 75 ms 672 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 88 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 76 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 72 ms 38228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 63 ms 38228 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 326 ms 38236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Execution timed out 2068 ms 38204 KB Time limit exceeded
48 Halted 0 ms 0 KB -