oj.uz

Submission #723384

# Submission time Handle Problem Language Result Execution time Memory
723384 2023-04-13T16:29:52 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 377036 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 (j) sum += (used>>c2&1) * suml[i][c2][j-1];
                    if (j <n)sum += (used>>c2&1) * 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 174 ms 376296 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 145 ms 376228 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 158 ms 376332 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 160 ms 376192 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 190 ms 376180 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 244 ms 376840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 227 ms 377004 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 233 ms 377036 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 238 ms 376908 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 376220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 209 ms 376212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 210 ms 376288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 208 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 180 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 181 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 217 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 191 ms 376228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 212 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 202 ms 376360 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 187 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 188 ms 376288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 188 ms 376176 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 198 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 188 ms 376288 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 180 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 196 ms 376288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 376220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 209 ms 376212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 210 ms 376288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 208 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 180 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 181 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 217 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 191 ms 376228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 212 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 202 ms 376360 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 187 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 188 ms 376288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 188 ms 376176 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 198 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 188 ms 376288 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 180 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 196 ms 376288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 163 ms 376168 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 169 ms 376264 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 227 ms 376240 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 199 ms 376244 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 199 ms 376268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 178 ms 376288 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 204 ms 376180 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 187 ms 376288 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 186 ms 376204 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 184 ms 376268 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 185 ms 376236 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 177 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 192 ms 376184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 200 ms 376360 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 174 ms 376296 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 180 ms 376296 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 191 ms 376232 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 202 ms 376368 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 182 ms 376364 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 488 ms 376440 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 324 ms 376400 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 291 ms 376312 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 371 ms 376356 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 435 ms 376360 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 830 ms 376356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1040 ms 376360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 545 ms 376444 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 518 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 667 ms 376416 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 376296 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 145 ms 376228 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 158 ms 376332 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 160 ms 376192 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 190 ms 376180 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 244 ms 376840 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 227 ms 377004 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 233 ms 377036 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 238 ms 376908 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 175 ms 376220 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 209 ms 376212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 210 ms 376288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 208 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 180 ms 376212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 181 ms 376268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 217 ms 376292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 191 ms 376228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 212 ms 376288 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 202 ms 376360 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 187 ms 376268 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 188 ms 376288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 188 ms 376176 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 198 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 188 ms 376288 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 180 ms 376396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 196 ms 376288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 163 ms 376168 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 169 ms 376264 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 227 ms 376240 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 199 ms 376244 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 199 ms 376268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 178 ms 376288 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 204 ms 376180 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 187 ms 376288 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 186 ms 376204 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 184 ms 376268 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 185 ms 376236 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 177 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 192 ms 376184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 200 ms 376360 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 174 ms 376296 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 180 ms 376296 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 191 ms 376232 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 202 ms 376368 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 182 ms 376364 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 488 ms 376440 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 324 ms 376400 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 291 ms 376312 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 371 ms 376356 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 435 ms 376360 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 830 ms 376356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 1040 ms 376360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 545 ms 376444 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 518 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 667 ms 376416 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 202 ms 376180 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 190 ms 376292 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 220 ms 376200 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 160 ms 376192 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 170 ms 376296 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 178 ms 376380 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 174 ms 376236 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 295 ms 376836 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 334 ms 376920 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 261 ms 376964 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 289 ms 376920 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 183 ms 376184 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 182 ms 376172 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 237 ms 376172 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 215 ms 376296 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 185 ms 376200 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 182 ms 376396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 219 ms 376288 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 197 ms 376280 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 237 ms 376212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 269 ms 376176 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 199 ms 376192 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 209 ms 376300 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 219 ms 376288 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 218 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 206 ms 376268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 224 ms 376168 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 217 ms 376200 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 206 ms 376348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 220 ms 376352 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 626 ms 376348 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 352 ms 376348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 308 ms 376348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 416 ms 376256 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 582 ms 376340 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 693 ms 376348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 983 ms 376344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 525 ms 376340 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 567 ms 376308 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 583 ms 376464 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1462 ms 376812 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 222 ms 376216 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 738 ms 376812 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 266 ms 376936 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 174 ms 376292 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1048 ms 376800 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2052 ms 376780 KB Time limit exceeded
103 Halted 0 ms 0 KB -