oj.uz

Submission #723268

# Submission time Handle Problem Language Result Execution time Memory
723268 2023-04-13T13:23:58 Z drdilyor Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 378048 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;
                if (j)
                    for (int c2 = 0; c2 < G; c2++)
                        if (used&1<<c2)
                            sum += suml[i][c2][j-1];
                for (int c2 = 0; c2 < G; c2++)
                    if (used&1<<c2)
                        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 66 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 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 42 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 63 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 235 ms 297244 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 302 ms 354948 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 279 ms 378040 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 306 ms 378048 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 57 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 178 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 220 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 87 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 75 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 164 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 134 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 140 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 136 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 114 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 129 ms 680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 134 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 138 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 126 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 133 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 127 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 57 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 178 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 220 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 87 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 75 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 164 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 134 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 140 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 136 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 114 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 129 ms 680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 134 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 138 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 126 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 133 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 127 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 64 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 51 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 176 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 209 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 82 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 81 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 155 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 127 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 140 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 134 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 117 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 129 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 136 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 132 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 124 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 133 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 126 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 96 ms 38164 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 82 ms 38228 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 537 ms 38152 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Execution timed out 2067 ms 38228 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 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 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 42 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 63 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 235 ms 297244 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 302 ms 354948 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 279 ms 378040 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 306 ms 378048 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 57 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 57 ms 948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 178 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 220 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 87 ms 948 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 75 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 164 ms 884 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 134 ms 672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 140 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 136 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 114 ms 676 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 129 ms 680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 134 ms 672 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 138 ms 668 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 126 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 133 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 127 ms 668 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 64 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 51 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 176 ms 944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 209 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 82 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 81 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 155 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 127 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 140 ms 672 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 134 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 117 ms 680 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 129 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 136 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 132 ms 672 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 124 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 133 ms 676 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 126 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 96 ms 38164 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 82 ms 38228 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 537 ms 38152 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Execution timed out 2067 ms 38228 KB Time limit exceeded
48 Halted 0 ms 0 KB -