제출 #714886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714886		ibrahim001	Boarding Passes (BOI22_passes)	C++14	100 / 100	572 ms	32804 KiB

passes

#include "bits/stdc++.h"
#define intt long long
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<intt,intt>
#define ld long double
using namespace std;
const int G = 16;
const int N = 2e5+5;
const ld inf = 1e18;
const ld one = 1;
const ld two = 2;
ld self[G][N];
int cnt[G][N];
ld psum[G][G][N];
vector<int>ind[G];
int mp[150], used[150];
ld cost(int j, vector<int> vb, int k){
    ld res = self[j][k];
    for ( int i : vb ){
        if ( i == j )   continue;
        res += psum[j][i][k];
    }
    return res;
}
int i,j;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int g = 0;
    for ( char c : s )  if ( !used[c] )   mp[c] = g++, used[c]=true;
    for ( i = 0; i < s.size(); i++ ){
        ind[mp[s[i]]].pb(i+1);
    }
    for ( int i = 0; i < g; i++ ){
        int sz = ind[i].size();
        self[i][0] = one*sz*(sz-1)/4;
        for ( j = 1; j <= sz; j++ ){
            self[i][j] = self[i][j-1]-(sz-j)/two + (j-1)/two;
        }
    }
    for ( i = 1; i <= n; i++ ){
        for ( j = 0; j < g; j++ ){
            cnt[j][i] = cnt[j][i-1];
        }
        cnt[mp[s[i-1]]][i]++;
    }
    for ( i = 0; i < g; i++ ){
        for ( j = 0; j < g; j++ ){
            if ( i == j )   continue;
            for ( int l : ind[i] ){
                psum[i][j][0] += cnt[j][n] - cnt[j][l];
            }
            for ( int l = 1; l <= ind[i].size(); l++ ){
                psum[i][j][l] = psum[i][j][l-1] - (cnt[j][n]-cnt[j][ind[i][l-1]]) + cnt[j][ind[i][l-1]];
            }
        }
    }
    vector<ld>dp(1<<g, 1e18);
    dp[0] = 0;
    for ( i = 1; i < (1<<g); i++ ){
        vector<int>vb;
        for ( j = 0; j < g; j++ ){
            if ( i&(1<<j) ) vb.pb(j);
        }
        for ( int j : vb ){
            int low = 0, high = ind[j].size(), mid, best;
            while (2 < high-low){
                mid = (low+high)>>1;
                ld c1 = cost(j, vb, mid), c2=cost(j, vb, mid+1);
                if ( c1 > c2 ){
                    low = mid;
                }
                else{
                    high = mid+1;
                }
            }
            ld mincost = inf;
            for ( int l = low; l <= high; l++ ) mincost = min(mincost, cost(j, vb, l));
            dp[i] = min(dp[i], dp[i^(1<<j)] + mincost);
        }
    }
    cout << setprecision(9) << fixed << dp[(1<<g)-1] << endl;
}

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

passes.cpp: In function 'int main()':
passes.cpp:35:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     for ( char c : s )  if ( !used[c] )   mp[c] = g++, used[c]=true;
      |                                    ^
passes.cpp:35:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     for ( char c : s )  if ( !used[c] )   mp[c] = g++, used[c]=true;
      |                                              ^
passes.cpp:35:61: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     for ( char c : s )  if ( !used[c] )   mp[c] = g++, used[c]=true;
      |                                                             ^
passes.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for ( i = 0; i < s.size(); i++ ){
      |                  ~~^~~~~~~~~~
passes.cpp:37:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         ind[mp[s[i]]].pb(i+1);
      |                    ^
passes.cpp:50:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         cnt[mp[s[i-1]]][i]++;
      |                      ^
passes.cpp:58:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for ( int l = 1; l <= ind[i].size(); l++ ){
      |                              ~~^~~~~~~~~~~~~~~~
passes.cpp:71:53: warning: unused variable 'best' [-Wunused-variable]
   71 |             int low = 0, high = ind[j].size(), mid, best;
      |                                                     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40