oj.uz

Submission #723267

# Submission time Handle Problem Language Result Execution time Memory
723267 2023-04-13T13:18:48 Z drdilyor Boarding Passes (BOI22_passes) C++17
5 / 100
 251 ms 378104 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;
                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]);
            }
        }
    };
    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 39 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 15 ms 592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 25 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 39 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 209 ms 297400 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 240 ms 354864 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 251 ms 378104 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 251 ms 378040 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 36 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 139 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 175 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 32 ms 852 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 36 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 139 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 175 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 32 ms 852 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 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 15 ms 592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 25 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 39 ms 4308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 209 ms 297400 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 240 ms 354864 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 251 ms 378104 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 251 ms 378040 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 30 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 36 ms 956 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 139 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 175 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Incorrect 32 ms 852 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
15 Halted 0 ms 0 KB -