oj.uz

Submission #723373

# Submission time Handle Problem Language Result Execution time Memory
723373 2023-04-13T16:22:37 Z drdilyor Boarding Passes (BOI22_passes) C++17
5 / 100
 230 ms 376916 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define time(code) {auto _s = chrono::high_resolution_clock::now(); code;cerr << (chrono::high_resolution_clock::now() - _s).count() / 1e9 << '\n';}
 
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    char a = 'A';
    string s; cin >> s;
    const int G = 15, N = 1e5;
    int n = s.size();
    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    ll suml[G][G][N];
    ll sumr[G][G][N];
    ll cr[G][N];
    ll cl[G][N];
    int cnt[G]{};
    vector ix(G, vector<int>());

    time(({
        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++)
            cnt[s[i] - a]++;
        for (int i = 0; i < G; i++)
            ix[i].reserve(cnt[i]);
        for (int i = 0; i < n ;i++) 
            ix[s[i] - a].push_back(i);
    }));

    ll memo[1<<G];
    memo[(1<<G)-1] = 0;
    for (int used = (1<<G)-1-1; used >= 0; used--) {
        ll& res = memo[used];
        res = 1e18;
        for (int i = 0 ;i < G; i++) {
            if (used&1<<i) continue;

            auto f = [&](int j) {
                ll sum = 0;
                for (int k = 0; k < G; k++) {
                    int c2 = k;
                    if (used>>c2&1) {
                        if (j) sum += suml[i][c2][j-1];
                        if (j <n)sum += sumr[i][c2][j];
                    }
                }
                return sum * 4 + (j < n ? exp_inv(cr[i][j]) : 0) + (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 = max(l-1, 0); j < min((int)ix[i].size(), 3 + max(0, r)); j++) {
                res = min(res, f(ix[i][j]) + memo[used |1<<i]);
            }
            res = min(res, f(0) + memo[used |1<<i]);
        }
    };
    ll ans;
    ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
    cout << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 376208 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 143 ms 376296 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 151 ms 376288 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 159 ms 376252 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 172 ms 376296 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 214 ms 376820 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 220 ms 376816 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 227 ms 376892 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 230 ms 376916 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 376196 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 176 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 208 ms 376204 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 200 ms 376180 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 173 ms 376284 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 173 ms 376196 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 176 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 208 ms 376204 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 200 ms 376180 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 173 ms 376284 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 164 ms 376208 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 143 ms 376296 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 151 ms 376288 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 159 ms 376252 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 172 ms 376296 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 214 ms 376820 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 220 ms 376816 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 227 ms 376892 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 230 ms 376916 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 173 ms 376196 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 176 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 208 ms 376204 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 200 ms 376180 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Incorrect 173 ms 376284 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
15 Halted 0 ms 0 KB -