oj.uz

Submission #722921

# Submission time Handle Problem Language Result Execution time Memory
722921 2023-04-13T05:41:05 Z dxz05 Boarding Passes (BOI22_passes) C++17
25 / 100
 21 ms 468 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(int n){
    return (long double) n * (n - 1) / 4.0;
}

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 = 1e18;

    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 = 1e18;
            for (int half = 0; half <= sz; half++){
                if (half > 0) sum_l += diff[half - 1];
                cur = min(cur, sum_l + 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;
        }

        ans = min(ans, tot);


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

    cout << ans << 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

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 20 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 13 ms 324 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 12 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 9 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 212 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 8 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 20 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 13 ms 324 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 12 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 17 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 9 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 212 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 8 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 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 21 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 13 ms 320 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 12 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 16 ms 320 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 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 7 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 7 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 7 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 316 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 7 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 212 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 Incorrect 1 ms 468 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -