oj.uz

Submission #723381

# Submission time Handle Problem Language Result Execution time Memory
723381 2023-04-13T16:26:05 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 376996 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;
            }
 
            ll cur = min(f(0), f(n));;
            for (int j = max(l-1, 0); j < min((int)ix[i].size(), 3 + max(0, r)); j++) {
                cur = min(cur, f(ix[i][j]));
            }
            res = min(res, cur + 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 196 ms 376268 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 137 ms 376268 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 164 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 198 ms 376216 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 179 ms 376348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 227 ms 376776 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 239 ms 376932 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 256 ms 376956 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 279 ms 376844 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 172 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 225 ms 376312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 204 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 188 ms 376360 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 180 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 220 ms 376364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 230 ms 376324 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 198 ms 376204 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 198 ms 376176 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 182 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 191 ms 376300 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 199 ms 376304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 207 ms 376248 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 189 ms 376408 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 189 ms 376196 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 199 ms 376208 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 172 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 225 ms 376312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 204 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 188 ms 376360 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 180 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 220 ms 376364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 230 ms 376324 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 198 ms 376204 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 198 ms 376176 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 182 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 191 ms 376300 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 199 ms 376304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 207 ms 376248 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 189 ms 376408 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 189 ms 376196 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 199 ms 376208 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 180 ms 376168 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 211 ms 376284 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 224 ms 376396 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 213 ms 376264 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 182 ms 376304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 171 ms 376216 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 236 ms 376268 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 191 ms 376444 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 193 ms 376276 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 204 ms 376276 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 186 ms 376384 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 195 ms 376180 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 186 ms 376324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 192 ms 376212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 192 ms 376256 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 195 ms 376408 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 190 ms 376272 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 200 ms 376268 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 182 ms 376236 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 319 ms 376352 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 267 ms 376448 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 255 ms 376320 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 276 ms 376364 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 286 ms 376396 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 369 ms 376268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 424 ms 376296 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 324 ms 376268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 301 ms 376368 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 364 ms 376352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 376268 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 137 ms 376268 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 164 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 198 ms 376216 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 179 ms 376348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 227 ms 376776 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 239 ms 376932 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 256 ms 376956 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 279 ms 376844 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 174 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 172 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 225 ms 376312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 204 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 188 ms 376360 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 180 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 220 ms 376364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 230 ms 376324 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 198 ms 376204 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 198 ms 376176 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 182 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 191 ms 376300 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 199 ms 376304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 207 ms 376248 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 189 ms 376408 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 189 ms 376196 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 199 ms 376208 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 180 ms 376168 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 211 ms 376284 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 224 ms 376396 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 213 ms 376264 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 182 ms 376304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 171 ms 376216 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 236 ms 376268 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 191 ms 376444 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 193 ms 376276 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 204 ms 376276 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 186 ms 376384 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 195 ms 376180 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 186 ms 376324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 192 ms 376212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 192 ms 376256 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 195 ms 376408 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 190 ms 376272 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 200 ms 376268 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 182 ms 376236 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 319 ms 376352 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 267 ms 376448 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 255 ms 376320 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 276 ms 376364 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 286 ms 376396 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 369 ms 376268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 424 ms 376296 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 324 ms 376268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 301 ms 376368 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 364 ms 376352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 178 ms 376248 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 177 ms 376264 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 178 ms 376176 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 142 ms 376356 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 161 ms 376232 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 169 ms 376204 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 179 ms 376296 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 226 ms 376792 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 234 ms 376908 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 236 ms 376848 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 238 ms 376996 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 164 ms 376284 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 173 ms 376172 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 210 ms 376172 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 208 ms 376388 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 178 ms 376252 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 171 ms 376176 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 214 ms 376192 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 188 ms 376392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 187 ms 376264 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 189 ms 376268 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 183 ms 376308 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 188 ms 376268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 186 ms 376228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 189 ms 376200 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 185 ms 376272 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 192 ms 376348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 191 ms 376188 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 184 ms 376252 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 191 ms 376396 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 310 ms 376448 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 273 ms 376352 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 244 ms 376268 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 278 ms 376352 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 316 ms 376436 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 400 ms 376344 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 397 ms 376400 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 334 ms 376440 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 303 ms 376256 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 337 ms 376336 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 703 ms 376804 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 204 ms 376196 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 457 ms 376784 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 261 ms 376848 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 181 ms 376284 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 525 ms 376844 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1820 ms 376748 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Execution timed out 2085 ms 376804 KB Time limit exceeded
104 Halted 0 ms 0 KB -