제출 #666507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666507		mychecksedad	Boarding Passes (BOI22_passes)	C++17	5 / 100	272 ms	1172 KiB

passes

/* 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;
 
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 0 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40