oj.uz

Submission #666509

# Submission time Handle Problem Language Result Execution time Memory
666509 2022-11-28T19:20:56 Z mychecksedad Boarding Passes (BOI22_passes) C++17
30 / 100
 128 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;
                }

                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:77:16: warning: unused variable 'aa' [-Wunused-variable]
   77 |     int T = 1, aa;
      |                ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 1 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 2 ms 1172 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 2 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
25.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 121 ms 304 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 95 ms 304 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 88 ms 312 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 128 ms 316 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 71 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 8 ms 332 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 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 9 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 328 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

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 121 ms 304 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 95 ms 304 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 88 ms 312 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 128 ms 316 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 71 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 8 ms 332 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 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 9 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 328 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 328 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 113 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 94 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 78 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 113 ms 308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 332 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 82 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 9 ms 340 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 9 ms 328 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 9 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 8 ms 332 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 9 ms 328 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 10 ms 328 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Incorrect 2 ms 460 KB 1st numbers differ - expected: '12497500.0000000000', found: '0.0000000000', error = '1.0000000000'
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 1 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 2 ms 1172 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 2 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 121 ms 304 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 95 ms 304 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 88 ms 312 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 128 ms 316 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 71 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 8 ms 332 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 8 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 8 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 9 ms 332 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 7 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 8 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 8 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 9 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 9 ms 328 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 328 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 113 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 94 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 78 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 113 ms 308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 332 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 82 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 9 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 8 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 328 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 9 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 8 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 8 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 8 ms 332 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 9 ms 328 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 10 ms 328 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Incorrect 2 ms 460 KB 1st numbers differ - expected: '12497500.0000000000', found: '0.0000000000', error = '1.0000000000'
45 Halted 0 ms 0 KB -