oj.uz

Submission #666507

# Submission time Handle Problem Language Result Execution time Memory
666507 2022-11-28T19:10:56 Z mychecksedad Boarding Passes (BOI22_passes) C++17
5 / 100
 272 ms 1172 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e5 + 100;

int n;
string s;
double dp[N];
vector<int> v[15];
void solve(){
    cin >> s; n = s.length();

    for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i);

    if(v[0].size() == n){
        double k1 = n/2;
        double k2 = (n+1)/2;
        cout << (k1*(k1-1) + (k2)*(k2-1))/4.0;
        return;
    }

    vector<int> p = {0, 1, 2, 3, 4, 5, 6};

    double best = -1;


    do{
        double S = 0;
        vector<bool> vis(n);
        for(int i = 0; i < 7; ++i){
            
            int a = v[p[i]].size();
            double best_k = -1;

            for(int k = 0; k <= a; ++k){
                double sum = 0;
                int po = 0, cur = 0;
                for(int j = 0; j < k; ++j){
                    while(po != n && po < v[p[i]][j]){
                        cur += vis[po];
                        po++;
                    }
                    sum += cur;
                }
                po = n - 1; cur = 0;
                for(int j = a - 1; j >= k; --j){
                    while(po != -1 && po > v[p[i]][j]){
                        cur += vis[po];
                        po--;
                    }
                    sum += cur;
                }
                for(double i = 2; i <= n; ++i) sum /= i;

                double k1 = a - k;
                double val = (k * (k-1) + k1*(k1-1))/4.0 + sum;
                best_k = (best_k == -1 ? val : min(val, best_k));
            }

            for(int pos: v[p[i]]) vis[pos] = 1;

            S += best_k;
        }
        
        best = (best == -1 ? S : min(best, S));

    }while(next_permutation(all(p)));

    cout << best;
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    setp();
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

passes.cpp: In function 'void solve()':
passes.cpp:17:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if(v[0].size() == n){
      |        ~~~~~~~~~~~~^~~~
passes.cpp: In function 'int main()':
passes.cpp:78:16: warning: unused variable 'aa' [-Wunused-variable]
   78 |     int T = 1, aa;
      |                ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1080 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1172 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1172 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 228 ms 312 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 272 ms 312 KB 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189'
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 228 ms 312 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 272 ms 312 KB 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1080 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1172 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1172 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 2 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 228 ms 312 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 272 ms 312 KB 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189'
13 Halted 0 ms 0 KB -