oj.uz

답안 #723267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -