oj.uz

Submission #722914

# Submission time Handle Problem Language Result Execution time Memory
722914 2023-04-13T05:32:50 Z dxz05 Boarding Passes (BOI22_passes) C++17
25 / 100
 90 ms 460 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);

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

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

            for (int i : pos[c]){
                int l = 0, r = 0;
                for (int j = 0; j < i; j++) l += used[j];
                for (int j = i + 1; j < n; j++) r += used[j];
                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));
            }

            for (int i : pos[c]) used[i] = true;

            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:42:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |             int sz = (int) pos[c].size();
      |                                ^
passes.cpp:44:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |             for (int i : pos[c]){
      |                              ^
passes.cpp:60:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |             for (int i : pos[c]) used[i] = true;
      |                              ^
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 212 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 68 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 60 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 65 ms 300 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 53 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 10 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 328 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 320 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 11 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 68 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 60 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 65 ms 300 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 53 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 10 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 10 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 328 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 10 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 320 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 11 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 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 65 ms 300 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 67 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 67 ms 308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 4 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 52 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 10 ms 372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 10 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 10 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 10 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 13 ms 328 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 10 ms 320 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 10 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 10 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 11 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 87 ms 460 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 90 ms 448 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 212 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -