oj.uz

답안 #948754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948754 2024-03-18T13:08:29 Z ifateen Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 1628 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<char, int> m;
signed main() {
    string s;
    cin >> s;
    vector<int> v(s.length());
    int cnt = 1;
    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));
    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(cnt);
        int n = s.length();
        for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
        vector<int> order;
        for (int i = 1; i <= G; ++i) order.push_back(i);
        long double ans = 1e18;
        do {
            long double EV = 0;
            set<int> vis;
            for (auto &i: order) {
                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 (vis.find(v[k]) != vis.end()) prev += 1;
                        else continue;
                    }
                    for (int k = n - 1; k > j; --k) {
                        if (v[k] == i) nd += 0.5;
                        else if (vis.find(v[k]) != vis.end()) nd += 1;
                        else continue;
                    }
                    EV += min(prev, nd);
                }
                vis.insert(i);
            }
            if (ans > EV) {
                ans = EV;
            }
        } while (next_permutation(begin(order), end(order)));
        cout << fixed << setprecision(8) << ans;
    }
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:10: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]
   10 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 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 3 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1380 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1628 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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 260 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 184 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 82 ms 436 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 160 ms 760 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 22 ms 436 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 22 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 25 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 21 ms 436 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 24 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 440 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 22 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 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 260 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 184 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 82 ms 436 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 160 ms 760 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 22 ms 436 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 22 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 25 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 21 ms 436 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 24 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 440 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 22 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 432 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 245 ms 420 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 200 ms 416 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 87 ms 412 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 4 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 156 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 4 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 23 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 23 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 24 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 22 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 21 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 24 ms 432 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 20 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 23 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 23 ms 424 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 348 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 Execution timed out 2031 ms 600 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 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 3 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1380 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1628 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 260 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 184 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 82 ms 436 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 4 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 160 ms 760 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 4 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 22 ms 436 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 22 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 25 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 21 ms 436 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 21 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 24 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 21 ms 440 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 22 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 24 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 432 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 245 ms 420 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 200 ms 416 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 87 ms 412 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 4 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 156 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 4 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 23 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 23 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 24 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 22 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 21 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 24 ms 432 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 20 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 23 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 23 ms 424 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2031 ms 600 KB Time limit exceeded
47 Halted 0 ms 0 KB -