oj.uz

Submission #1098933

# Submission time Handle Problem Language Result Execution time Memory
1098933 2024-10-10T10:48:55 Z not_amir Boarding Passes (BOI22_passes) C++14
30 / 100
 9 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    long long n = S.size();
    bool h[7];
    for(char c : S) {
        h[c- 'A'] = 1;
    }
    vector<char> v;
    for(int i = 0; i < 7; i++)
        if(h[i])
            v.push_back('A' + i);
    ll res = n * n;
    do {
        ll tot = 0;
        vector<bool> on(n);
        vector<ll> rem(n);
        for(int j = 0; j < v.size(); j++) {
            ll ans = 0;
            for(int i = 0, it = 0, sum = 0; i < n; i++) {
                if(S[i] == v[j]) {
                    rem[i] = it++ + 2 * sum;
                    ans += rem[i];
                }
                else if(on[i])
                    sum++;
            }
            ll mini = ans;
            for(int i = n - 1, it = 0, sum = 0; i>= 0; i--) {
                if(S[i] == v[j]) {
                    ans -= rem[i];
                    ans += it++ + 2 * sum;
                    on[i] = 1;
                }
                else if(on[i])
                    sum++;
                mini = min(mini, ans);
            }
            tot += mini;
        }
        res = min(res, tot);
    } while(next_permutation(v.begin(), v.end()));
    cout << fixed << setprecision(6) << ld(res) / 2.0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j = 0; j < v.size(); j++) {
      |                        ~~^~~~~~~~~~

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 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 1 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1112 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 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 8 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 348 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 6 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 456 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 460 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 456 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 8 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 348 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 6 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 456 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 460 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 456 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 9 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 8 ms 452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 8 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 7 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 456 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Runtime error 1 ms 604 KB Execution killed with signal 6
36 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 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 1 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1112 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 1372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 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 8 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 8 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 8 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 6 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 3 ms 456 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 3 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 3 ms 460 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 3 ms 456 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 9 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 8 ms 452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 8 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 7 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 456 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 3 ms 452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 3 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Runtime error 1 ms 604 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -