oj.uz

Submission #723382

# Submission time Handle Problem Language Result Execution time Memory
723382 2023-04-13T16:28:36 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 377020 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(), 2 + 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 181 ms 376168 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 150 ms 376188 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 162 ms 376268 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 176 ms 376220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 182 ms 376400 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 225 ms 376780 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 241 ms 376900 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 241 ms 376812 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 234 ms 376800 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 376396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 192 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 210 ms 376376 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 218 ms 376284 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 186 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 174 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 217 ms 376208 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 199 ms 376188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 200 ms 376328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 209 ms 376376 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 196 ms 376284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 210 ms 376216 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 209 ms 376292 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 222 ms 376288 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 232 ms 376284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 204 ms 376252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 202 ms 376268 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 376396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 192 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 210 ms 376376 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 218 ms 376284 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 186 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 174 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 217 ms 376208 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 199 ms 376188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 200 ms 376328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 209 ms 376376 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 196 ms 376284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 210 ms 376216 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 209 ms 376292 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 222 ms 376288 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 232 ms 376284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 204 ms 376252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 202 ms 376268 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 233 ms 376292 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 208 ms 376288 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 239 ms 376288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 222 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 267 ms 376296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 185 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 238 ms 376236 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 204 ms 376256 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 241 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 232 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 250 ms 376364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 245 ms 376268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 224 ms 376184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 232 ms 376232 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 226 ms 376292 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 255 ms 376236 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 256 ms 376292 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 234 ms 376324 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 223 ms 376368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 366 ms 376236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 342 ms 376360 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 294 ms 376372 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 319 ms 376360 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 325 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 525 ms 376356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 590 ms 376360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 373 ms 376396 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 372 ms 376356 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 430 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 181 ms 376168 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 150 ms 376188 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 162 ms 376268 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 176 ms 376220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 182 ms 376400 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 225 ms 376780 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 241 ms 376900 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 241 ms 376812 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 234 ms 376800 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 178 ms 376396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 192 ms 376292 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 210 ms 376376 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 218 ms 376284 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 186 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 174 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 217 ms 376208 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 199 ms 376188 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 200 ms 376328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 209 ms 376376 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 196 ms 376284 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 210 ms 376216 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 209 ms 376292 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 222 ms 376288 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 232 ms 376284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 204 ms 376252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 202 ms 376268 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 233 ms 376292 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 208 ms 376288 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 239 ms 376288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 222 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 267 ms 376296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 185 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 238 ms 376236 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 204 ms 376256 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 241 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 232 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 250 ms 376364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 245 ms 376268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 224 ms 376184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 232 ms 376232 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 226 ms 376292 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 255 ms 376236 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 256 ms 376292 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 234 ms 376324 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 223 ms 376368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 366 ms 376236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 342 ms 376360 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 294 ms 376372 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 319 ms 376360 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 325 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 525 ms 376356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 590 ms 376360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 373 ms 376396 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 372 ms 376356 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 430 ms 376352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 210 ms 376288 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 208 ms 376256 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 206 ms 376176 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 172 ms 376240 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 204 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 212 ms 376292 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 210 ms 376300 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 266 ms 376880 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 279 ms 376992 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 305 ms 376988 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 271 ms 377020 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 191 ms 376176 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 236 ms 376268 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 257 ms 376256 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 227 ms 376184 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 202 ms 376252 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 188 ms 376260 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 223 ms 376288 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 200 ms 376268 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 212 ms 376212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 234 ms 376288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 214 ms 376220 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 227 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 232 ms 376292 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 208 ms 376292 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 214 ms 376184 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 220 ms 376288 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 230 ms 376288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 212 ms 376364 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 196 ms 376368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 460 ms 376360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 324 ms 376260 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 259 ms 376424 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 342 ms 376364 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 383 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 471 ms 376248 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 513 ms 376356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 389 ms 376252 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 365 ms 376364 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 407 ms 376360 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 830 ms 376908 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 251 ms 376300 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 486 ms 376904 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 336 ms 377016 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 194 ms 376308 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 601 ms 376896 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2089 ms 376868 KB Time limit exceeded
103 Halted 0 ms 0 KB -