oj.uz

Submission #674521

# Submission time Handle Problem Language Result Execution time Memory
674521 2022-12-24T16:47:44 Z stanislavpolyn Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 39104 KB 
#include <bits/stdc++.h>
 
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
 
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
 
using namespace std;
 
mt19937_64 rng(228);
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
 
const int N = 1e5 + 5;
 
string s;
ve<int> v[26];
 
ld dp[pw(16)];
int pref[N][16];
int suff[N][16];
ve<int> p;

ll P[N][16];
ll S[N][16];
int last[16];

ld get(int mask, int i, int x) {
    ll ans = 0;
    if (x > 0) {
        fr (cur, 0, 15) {
            if (mask & pw(cur)) {
                ans += P[v[i][x - 1]][p[cur]];
            }
        }
    }
    if (x < sz(v[i])) {
        fr (cur, 0, 15) {
            if (mask & pw(cur)) {
                ans += S[v[i][x]][p[cur]];
            }
        }
    }
    ld res = ans;
    res += ld(0.5) * (1LL * x * (x - 1) / 2);
    res += ld(0.5) * (1LL * (sz(v[i]) - x) * (sz(v[i]) - x - 1) / 2);

    return res;
}
 
ld calc(int mask, int i) {
    ld best = 1e18;

    fr (take, 0, sz(v[i])) {
        umn(best, get(mask, i, take));
    }

    return best;
}
 
int main() {
#ifdef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif
    cin >> s;
 
    fr (i, 0, sz(s) - 1) {
        v[s[i] - 'A'].pb(i);
    }
 
    fr (i, 0, sz(s) - 1) {
        pref[i][s[i] - 'A'] = 1;
        if (i > 0) {
            fr (j, 0, 15) {
                pref[i][j] += pref[i - 1][j];
            }
        }
    }
    rf (i, sz(s) - 1, 0) {
        suff[i][s[i] - 'A'] = 1;
        if (i + 1 < sz(s)) {
            fr (j, 0, 15) {
                suff[i][j] += suff[i + 1][j];
            }
        }
    }

    {
        fill(last, last + 16, -1);
        fr (i, 0, sz(s) - 1) {
            fr (j, 0, 15) {
                P[i][j] = pref[i][j];
            }
            if (last[s[i] - 'A'] != -1) {
                fr (j, 0, 15) {
                    P[i][j] += P[last[s[i] - 'A']][j];
                }
            }

            last[s[i] - 'A'] = i;
        }
        fill(last, last + 16, -1);
        rf (i, sz(s) - 1, 0) {
            fr (j, 0, 15) {
                S[i][j] = suff[i][j];
            }
            if (last[s[i] - 'A'] != -1) {
                fr (j, 0, 15) {
                    S[i][j] += S[last[s[i] - 'A']][j];
                }
            }

            last[s[i] - 'A'] = i;
        }
    }
 
 
    fr (i, 0, 25) {
        if (sz(v[i])) {
            p.pb(i);
        }
    }
 
    fr (mask, 0, pw(sz(p)) - 1) {
        dp[mask] = 1e18;
    }
    dp[0] = 0;
 
    fr (mask, 0, pw(sz(p)) - 1) {
        fr (i, 0, sz(p) - 1) {
            if (!(mask & pw(i))) {
                umn(dp[mask | pw(i)], dp[mask] + calc(mask, p[i]));
            }
        }
    }
    cout << fixed << setprecision(10) << dp[pw(sz(p)) - 1] << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 30516 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 24 ms 36396 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 26 ms 38696 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 26 ms 38668 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 3 ms 4180 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 3 ms 4180 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 195 ms 4212 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 166 ms 4180 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 163 ms 4240 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 182 ms 4180 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 189 ms 4180 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 229 ms 4052 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 187 ms 4136 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 196 ms 4132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 185 ms 4136 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 191 ms 4132 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 30516 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 24 ms 36396 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 26 ms 38696 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 26 ms 38668 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 3 ms 4180 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 3 ms 4180 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 195 ms 4212 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 166 ms 4180 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 163 ms 4240 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 182 ms 4180 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 189 ms 4180 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 229 ms 4052 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 187 ms 4136 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 196 ms 4132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 185 ms 4136 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 191 ms 4132 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 340 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 42 ms 868 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 23 ms 30512 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 25 ms 36348 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 27 ms 38644 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 27 ms 38676 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 ms 4180 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 3 ms 4180 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 209 ms 4208 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 178 ms 4180 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 188 ms 4180 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 175 ms 4180 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 204 ms 4180 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 187 ms 4136 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 188 ms 4052 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 195 ms 4128 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 210 ms 4148 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 187 ms 4132 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2097 ms 39104 KB Time limit exceeded
97 Halted 0 ms 0 KB -