oj.uz

Submission #949774

# Submission time Handle Problem Language Result Execution time Memory
949774 2024-03-19T16:53:03 Z sysia Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 31988 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
typedef long double ld;

void solve(){
    string s; cin >> s;
    int n = (int)s.size();
    vector<int>used(K);
    for (auto c: s) used[c-'A']++;
    vector<int>scale(K);
    int G = 0;
    for (int i = 0; i<K; i++) if (used[i]) scale[i] = G++;
    debug(G); //grupy [0, G-1]
    vector<vector<int>>what(G);
    for (int i = 0; i<n; i++) {
        what[scale[s[i]-'A']].emplace_back(i);
    }
    vector<ld>dp((1<<G), oo);
    dp[0] = 0;
    vector left(n, vector<int>(G)), right(n, vector<int>(G)); //dla i-tego indeksu grupa g doklada left[i] elementow z lewej
    for (int i = 0; i<n; i++){
        for (int g = 0; g < G; g++){
            if (scale[s[i]-'A'] == g) continue;
            int t = (int)(lower_bound(what[g].begin(), what[g].end(), i)-what[g].begin());
            left[i][g] = t;
            right[i][g] = (int)what[g].size()-t;
        }
    }
    for (int mask = 0; mask < (1<<G); mask++){
        debug(mask, dp[mask]);
        for (int i = 0; i<G; i++){
            if (mask&(1<<i)) continue;
            debug(mask, i);
            //dokladam grupe i --> to sie wydarzy 2^{G-1} razy
            int k = (int)what[i].size();
            long double curr = 0;
            for (int rep = 0; rep < k; rep++){ //kGlog n
                ld L = (ld)rep/2.0;
                ld R = (k-rep-1)/2.0;
                for (int t = 0; t < G; t++){
                    if (mask&(1<<t)){
                        L += left[what[i][rep]][t];
                        R += right[what[i][rep]][t];
                    }
                }
                debug(L, R);
                curr += min(L, R);
            }
            dp[mask^(1<<i)] = min(dp[mask^(1<<i)], dp[mask] + curr);
        }
    }
    cout << fixed << setprecision(10) << dp.back() << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 456 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 10 ms 9824 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 11 ms 11540 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 12 ms 12308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 12 ms 12308 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 344 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 456 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 1 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 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 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 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 344 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 456 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 1 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 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 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 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 360 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 348 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 0 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 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 548 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 456 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 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 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 1628 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 1628 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 97 ms 2944 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 58 ms 2904 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 55 ms 2904 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 64 ms 2908 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 93 ms 2916 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 105 ms 2912 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 100 ms 2908 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 88 ms 2904 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 107 ms 2904 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 100 ms 2920 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 348 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 1 ms 456 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 10 ms 9824 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 11 ms 11540 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 12 ms 12308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 12 ms 12308 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 348 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 0 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 456 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 360 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 2 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 548 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 456 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 1628 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 1628 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 97 ms 2944 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 58 ms 2904 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 55 ms 2904 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 64 ms 2908 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 93 ms 2916 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 105 ms 2912 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 100 ms 2908 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 88 ms 2904 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 107 ms 2904 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 100 ms 2920 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 0 ms 344 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 26 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 10 ms 9748 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 12 ms 11540 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 16 ms 12308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 15 ms 12288 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 456 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 2 ms 1624 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 2 ms 1624 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 107 ms 2908 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 61 ms 2908 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 60 ms 2924 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 65 ms 2912 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 105 ms 2904 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 102 ms 2908 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 115 ms 2908 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 102 ms 2904 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 101 ms 2904 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 105 ms 2916 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2040 ms 31988 KB Time limit exceeded
97 Halted 0 ms 0 KB -