oj.uz

Submission #1098932

# Submission time Handle Problem Language Result Execution time Memory
1098932 2024-10-10T10:43:38 Z not_amir Boarding Passes (BOI22_passes) C++14
0 / 100
 1 ms 348 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;
    while(next_permutation(v.begin(), v.end())) {
        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);
    }
    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
0 / 5.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 348 KB 1st numbers differ - expected: '1225.0000000000', found: '5000.0000000000', error = '3.0816326531'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 348 KB 1st numbers differ - expected: '1225.0000000000', found: '5000.0000000000', error = '3.0816326531'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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