oj.uz

Submission #723383

# Submission time Handle Problem Language Result Execution time Memory
723383 2023-04-13T16:28:47 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 230 ms 376296 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 179 ms 376264 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 242 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 200 ms 376188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 221 ms 376232 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 263 ms 377008 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 283 ms 376988 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 275 ms 376904 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 322 ms 377020 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 376176 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 208 ms 376288 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 255 ms 376316 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 252 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 213 ms 376292 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 200 ms 376264 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 249 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 223 ms 376256 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 233 ms 376228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 207 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 231 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 292 ms 376296 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 224 ms 376332 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 240 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 226 ms 376208 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 208 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 234 ms 376204 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 376176 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 208 ms 376288 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 255 ms 376316 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 252 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 213 ms 376292 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 200 ms 376264 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 249 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 223 ms 376256 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 233 ms 376228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 207 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 231 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 292 ms 376296 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 224 ms 376332 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 240 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 226 ms 376208 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 208 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 234 ms 376204 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 238 ms 376216 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 205 ms 376256 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 264 ms 376292 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 237 ms 376268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 210 ms 376356 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 209 ms 376184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 264 ms 376340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 233 ms 376364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 255 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 244 ms 376288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 238 ms 376288 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 262 ms 376384 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 224 ms 376396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 217 ms 376240 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 237 ms 376288 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 208 ms 376188 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 194 ms 376224 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 207 ms 376340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 204 ms 376272 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 374 ms 376364 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 305 ms 376436 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 279 ms 376352 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 328 ms 376440 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 335 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 418 ms 376352 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 525 ms 376356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 479 ms 376376 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 357 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 453 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 230 ms 376296 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 179 ms 376264 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 242 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 200 ms 376188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 221 ms 376232 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 263 ms 377008 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 283 ms 376988 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 275 ms 376904 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 322 ms 377020 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 205 ms 376176 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 208 ms 376288 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 255 ms 376316 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 252 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 213 ms 376292 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 200 ms 376264 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 249 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 223 ms 376256 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 233 ms 376228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 207 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 231 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 292 ms 376296 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 224 ms 376332 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 240 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 226 ms 376208 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 208 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 234 ms 376204 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 238 ms 376216 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 205 ms 376256 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 264 ms 376292 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 237 ms 376268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 210 ms 376356 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 209 ms 376184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 264 ms 376340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 233 ms 376364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 255 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 244 ms 376288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 238 ms 376288 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 262 ms 376384 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 224 ms 376396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 217 ms 376240 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 237 ms 376288 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 208 ms 376188 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 194 ms 376224 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 207 ms 376340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 204 ms 376272 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 374 ms 376364 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 305 ms 376436 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 279 ms 376352 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 328 ms 376440 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 335 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 418 ms 376352 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 525 ms 376356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 479 ms 376376 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 357 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 453 ms 376352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 213 ms 376292 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 189 ms 376248 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 219 ms 376288 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 209 ms 376180 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 203 ms 376176 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 191 ms 376272 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 202 ms 376300 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 266 ms 376852 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 266 ms 376988 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 258 ms 377000 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 281 ms 376988 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 189 ms 376364 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 196 ms 376300 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 247 ms 376340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 229 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 209 ms 376196 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 210 ms 376300 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 233 ms 376356 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 274 ms 376180 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 204 ms 376176 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 217 ms 376288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 214 ms 376304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 214 ms 376268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 219 ms 376304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 225 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 205 ms 376248 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 219 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 221 ms 376300 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 216 ms 376268 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 209 ms 376240 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 405 ms 376360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 305 ms 376364 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 258 ms 376248 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 305 ms 376252 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 316 ms 376324 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 467 ms 376348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 522 ms 376352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 366 ms 376356 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 357 ms 376244 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 380 ms 376256 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 809 ms 376836 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 224 ms 376292 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 526 ms 376792 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 259 ms 376920 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 199 ms 376256 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 612 ms 376824 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2066 ms 376788 KB Time limit exceeded
103 Halted 0 ms 0 KB -