oj.uz

Submission #920651

# Submission time Handle Problem Language Result Execution time Memory
920651 2024-02-02T20:38:40 Z themm1 Boarding Passes (BOI22_passes) C++17
55 / 100
 409 ms 1116 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

bool ith_bit(int x, int i) {
        int y = (1 << i);
        return (x ^ y) < x;
}

void print_bits(int x) {
        bitset<8> bx = x;
        cout << bx << endl;
}

void solve() {
        string s;
        cin >> s;
        int N = sz(s);
        vector<int> mapping(26, -1);
        int M = 0;
        for (int i = 0; i < N; i++) {
                if (mapping[s[i] - 'A'] == -1) {
                        mapping[s[i] - 'A'] = M;
                        M++;
                }
        }
        int M2 = (1 << M);

        vector<ld> dp(M2, N * N);
        dp[0] = 0;
        for (int mask = 1; mask < M2; mask++) {
                // print_bits(mask);
                for (int i = 0; i < M; i++) if (ith_bit(mask, i) == 1) {
                        // dmp(i);
                        int i2 = 1 << i;
                        vector<int> a(N, 0);
                        int suff_sum = 0;
                        for (int j = 0; j < N; j++) {
                                if (ith_bit(mask, mapping[s[j] - 'A'])) {
                                        if (mapping[s[j] - 'A'] == i) a[j] = 1;
                                        else a[j] = 2;
                                }
                                suff_sum += a[j];
                        }
                        // dmp(a);
                        ld prev = dp[mask ^ i2], curr = 0;
                        int pref_sum = 0;
                        for (int j = 0; j < N; j++) {
                                suff_sum -= a[j];
                                if (mapping[s[j] - 'A'] == i) {
                                        ld val = (ld)min(pref_sum, suff_sum) / (ld)2;
                                        curr += val;
                                }
                                pref_sum += a[j];
                        }
                        dp[mask] = min(dp[mask], prev + curr);
                }
        }
        ld ans = dp[M2 - 1];
        cout << ans << endl;
}

int32_t main() {
        ios::sync_with_stdio(false);
        cout << setprecision(12);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 1 ms 1116 KB 1st numbers differ - expected: '1100977812.5000000000', found: '218075609.0000000000', error = '0.8019255188'
8 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 504 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 472 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 409 ms 516 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 116 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 107 ms 348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 106 ms 348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 129 ms 596 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 123 ms 524 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 121 ms 348 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 122 ms 520 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 123 ms 520 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 130 ms 516 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 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 1 ms 1116 KB 1st numbers differ - expected: '1100977812.5000000000', found: '218075609.0000000000', error = '0.8019255188'
8 Halted 0 ms 0 KB -