oj.uz

Submission #948761

# Submission time Handle Problem Language Result Execution time Memory
948761 2024-03-18T13:18:35 Z ifateen Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<char, int> m;
long double dp[1 << 20];
signed main() {
    string s;
    cin >> s;
    vector<int> v(s.length());
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
    }
    int G = *max_element(begin(v), end(v)) + 1;
    if (G == 1) {
        long double n = s.length();
        long double a = floor(n / 2), b = ceil(n / 2);
        cout << fixed << setprecision(8) << (a * (a - 1) + b * (b - 1)) / 4.0;
    } else {
        vector<vector<int>> pos(G);
        int n = s.length();
        for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
        dp[0] = 0;
        for (int mask = 1; mask < (1 << G); mask++) {
            dp[mask] = 1e18;
            for (int i = 0; i < G; i++) {
                if (!(mask & (1 << i))) continue;
                long double EV = 0;
                for (auto &j: pos[i]) {
                    long double prev = 0, nd = 0;
                    for (int k = 0; k < j; ++k) {
                        if (v[k] == i) prev += 0.5;
                        else if (mask & (1 << v[k])) prev += 1;
                        else continue;
                    }
                    for (int k = n - 1; k > j; --k) {
                        if (v[k] == i) nd += 0.5;
                        else if (mask & (1 << v[k])) nd += 1;
                        else continue;
                    }
                    EV += min(prev, nd);
                }
                dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
            }
        }
        cout << fixed << setprecision(8) << dp[(1 << G) - 1];
    }
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:11:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 500 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 2 ms 1116 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1372 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 344 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 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 344 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 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
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 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 344 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 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 344 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 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 2 ms 344 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 344 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 0 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 0 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 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 344 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 408 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 0 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 0 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2057 ms 604 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 500 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 2 ms 1116 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1372 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 344 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 344 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 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 344 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 0 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 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 344 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 408 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 0 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 0 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2057 ms 604 KB Time limit exceeded
47 Halted 0 ms 0 KB -