oj.uz

Submission #722924

# Submission time Handle Problem Language Result Execution time Memory
722924 2023-04-13T05:45:06 Z dxz05 Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 1936 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long double exp_inv(ll n){
    return (long double) n * (n - 1); // should be divided by 4
}

vector<int> pos[140];

void solve(){
    string s;
    cin >> s;
    int n = (int)s.size();

    string alphabet;
    for (int i = 0; i < n; i++){
        if (pos[s[i]].empty()) alphabet += s[i];
        pos[s[i]].push_back(i);
    }

    sort(all(alphabet));

    int m1 = (n - 1) / 2;
    int m2 = m1 + 1;

    long double ans = 5e18;

    do {
        long double tot = 0;
        vector<bool> used(n, false);
        vector<int> cnt(n, 0);

        for (char c : alphabet){
            ll sum_l = 0;
            vector<int> diff;

            int sz = (int) pos[c].size();

            for (int i : pos[c]){
                int l = cnt[i];
                int r = cnt.back() - cnt[i];
                sum_l += l;
                diff.push_back(r - l);
            }

            sort(all(diff));

            long double cur = 5e18;
            for (int half = 0; half <= sz; half++){
                if (half > 0) sum_l += diff[half - 1];
                cur = min(cur, sum_l * 4 + exp_inv(half) + exp_inv(sz - half));
            }

            int j = 0;
            for (int i = 0; i < n; i++){
                while (j < sz && pos[c][j] <= i) j++;
                cnt[i] += j;
            }

            tot += cur;

            if (tot > ans) break;
        }

        ans = min(ans, tot);


    } while (next_permutation(all(alphabet)));

    cout << fixed << setprecision(5);
    cout << (long double) ans / 4.0 << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Compilation message

passes.cpp: In function 'void solve()':
passes.cpp:23:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (pos[s[i]].empty()) alphabet += s[i];
      |                     ^
passes.cpp:24:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         pos[s[i]].push_back(i);
      |                 ^
passes.cpp:43:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |             int sz = (int) pos[c].size();
      |                                ^
passes.cpp:45:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |             for (int i : pos[c]){
      |                              ^
passes.cpp:62:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                 while (j < sz && pos[c][j] <= i) j++;
      |                                      ^
passes.cpp:30:9: warning: unused variable 'm2' [-Wunused-variable]
   30 |     int m2 = m1 + 1;
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1936 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1936 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 21 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 7 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 316 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 320 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 212 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 21 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 7 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 316 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 320 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 23 ms 324 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 10 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 12 ms 324 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 316 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 18 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 7 ms 316 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 9 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 7 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 7 ms 320 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 7 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 7 ms 316 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2051 ms 468 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1936 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1936 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 22 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 11 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 11 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 21 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 7 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 7 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 7 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 8 ms 316 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 7 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 7 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 9 ms 320 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 7 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 7 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 23 ms 324 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 10 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 12 ms 324 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 3 ms 316 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 18 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 8 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 7 ms 316 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 9 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 7 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 7 ms 320 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 7 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 7 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 7 ms 316 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2051 ms 468 KB Time limit exceeded
47 Halted 0 ms 0 KB -