oj.uz

Submission #789008

# Submission time Handle Problem Language Result Execution time Memory
789008 2023-07-20T20:14:14 Z Ozy Boarding Passes (BOI22_passes) C++17
0 / 100
 2000 ms 340 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << fixed << setprecision(1) << a << endl
#define debugsl(a) cout << #a << " = " << fixed << setprecision(1) << a << ", "
#define rep(i,a,b) for(int i = (a); i<=(b); i++)
#define repa(i,a,b) for(int i = (a); i>=(b); i--)
#define pll pair<lli,lli>

#define MAX 100000
#define G 7

lli n,k,arr[MAX+2],cont,p_[G+2],vis[G+2],sum[G+2];
long double dp[MAX+2],res,a;
string st;
map<char,lli> mapa;
vector<lli> orden;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> st;
    n = st.size();

    cont = 1;
    rep(i,1,n) {
        if (mapa.find((char)st[i-1]) == mapa.end()) mapa[(char)st[i-1]] = cont++;
        arr[i] = mapa[st[i-1]];

        a = (i-1);
        a /= 2;
        dp[i] = dp[i-1] + a;
    }

    res = -1;
    rep(mitad,1,n) {
        //debug(mitad);

        orden.clear();
        rep(i,1,G) orden.push_back(i);

        do {
            cont = 1;
            rep(i,0,G-1) {
                //debug(orden[i]);
                p_[orden[i]] = cont++;
            }

            long double sub_res = 0;
            rep(i,1,G) sum[i] = 0;
            rep(i,1,mitad-1) {
                rep(j,1,p_[arr[i]]-1) sub_res += sum[j];
                sum[p_[arr[i]]]++;
            }
            //debugsl(sub_res);
            rep(i,1,G) sub_res += dp[sum[i]];
            //debug(sub_res);

            rep(i,1,G) sum[i] = 0;
            repa(i,n,mitad) {
                rep(j,1,p_[arr[i]]-1) sub_res += sum[j];
                sum[p_[arr[i]]]++;
            }
            //debugsl(sub_res);
            rep(i,1,G) sub_res += dp[sum[i]];
            //debug(sub_res);
            if (res == -1 || sub_res < res) res = sub_res;

        } while (next_permutation(orden.begin(), orden.end()));
    }

    cout << fixed << setprecision(3) << res;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 264 ms 332 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 480 ms 320 KB 1st numbers differ - expected: '1023.0000000000', found: '1023.5000000000', error = '0.0004887586'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 264 ms 332 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 480 ms 320 KB 1st numbers differ - expected: '1023.0000000000', found: '1023.5000000000', error = '0.0004887586'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -