oj.uz

Submission #723271

# Submission time Handle Problem Language Result Execution time Memory
723271 2023-04-13T13:30:15 Z drdilyor Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 378188 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);

    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 = (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]);
            }
            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";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 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 32 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 34 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 46 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 278 ms 297228 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 263 ms 354980 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 275 ms 378188 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 261 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 40 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 130 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 123 ms 932 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 42 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 37 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 105 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 73 ms 684 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 74 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 81 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 68 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 76 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 73 ms 668 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 82 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 66 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 71 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 85 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 130 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 123 ms 932 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 42 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 37 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 105 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 73 ms 684 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 74 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 81 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 68 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 76 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 73 ms 668 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 82 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 66 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 71 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 85 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 42 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 46 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 117 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 134 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 43 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 48 ms 624 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 110 ms 880 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 67 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 75 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 78 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 73 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 79 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 80 ms 676 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 74 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 64 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 67 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 80 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 68 ms 38236 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 66 ms 38220 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 303 ms 38236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Execution timed out 2064 ms 38240 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 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 32 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 34 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 46 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 278 ms 297228 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 263 ms 354980 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 275 ms 378188 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 261 ms 378044 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 40 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 42 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 130 ms 940 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 123 ms 932 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 42 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 37 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 105 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 73 ms 684 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 74 ms 668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 81 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 68 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 76 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 73 ms 668 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 82 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 66 ms 668 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 71 ms 668 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 85 ms 672 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 42 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 46 ms 944 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 117 ms 936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 134 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 43 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 48 ms 624 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 110 ms 880 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 67 ms 680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 75 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 78 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 73 ms 672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 79 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 80 ms 676 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 74 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 64 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 67 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 80 ms 680 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 68 ms 38236 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 66 ms 38220 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 303 ms 38236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Execution timed out 2064 ms 38240 KB Time limit exceeded
48 Halted 0 ms 0 KB -