Submission #711191

#	Time	Username	Problem	Language	Result	Execution time	Memory
711191		rrrr10000	Boarding Passes (BOI22_passes)	C++14	5 / 100	3 ms	596 KiB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

int main(){
    string str;cin>>str;
    ll n=15,m=str.size();
    {
        ll ok=-1,ng=m;
        while(ng-ok>1){
            ll md=(ok+ng)/2;
            if(md<m-1-md)ok=md;
            else ng=md;
        }
        ll ans=(ok+1)*ok/2+(m-ok-1)*(m-ok-2)/2;
        if(ans%2==0)out(ans/2);
        else{
            cout<<ans/2;
            cout<<".5"<<endl;
        }
    }
    // vvi g(n);
    // rep(i,m)g[str[i]-'A'].pb(i);
    // vvp cost(n,vp(m));
    // rep(i,n){
    //     ll cnt=0;
    //     rep(j,m){
    //         if(str[j]-'A'==i)cnt++;
    //         cost[i][j]=P(cnt*2,(g[i].size()-cnt)*2);
    //     }
    // }
    // vvp rui=cost;
    // rep(i,n)rep(j,n)rep(k,g[j].size()-1)rui[i][g[j][k+1]].fi+=rui[i][g[j][k]].fi;
    // rep(i,n)rep(j,n)for(ll k=g[j].size()-1;k>0;k--)rui[i][g[j][k-1]].se+=rui[i][g[j][k]].se;
    // vi dp(1<<n,1001001001001001001);
    // dp[0]=0;
    // rep(bit,1<<n){
    //     rep(i,n)if(!(bit>>i&1)){
    //         ll ok=-1,ng=g[i].size();
    //         while(ng-ok>1){
    //             ll md=(ok+ng)/2;
    //             ll cost0=md,cost1=g[i].size()-1-md;
    //             rep(j,n)if(bit>>j&1){
    //                 cost0+=cost[j][g[i][md]].fi;
    //                 cost1+=cost[j][g[i][md]].se;
    //             }
    //             if(cost0<cost1)ok=md;
    //             else ng=md;
    //         }
    //         ll ncost=dp[bit]+(ok+1)*ok/2+(g[i].size()-ok-1)*(g[i].size()-ok-2)/2;
    //         if(ok!=-1){
    //             rep(j,n)if(bit>>j&1)ncost+=rui[j][g[i][ok]].fi;
    //         }
    //         if(ng!=g[i].size()){
    //             rep(j,n)if(bit>>j&1)ncost+=rui[j][g[i][ng]].se;
    //         }
    //         chmin(dp[bit|(1<<i)],ncost);
    //     }
    // }
    // out((long double)(dp.back())/2);
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:25:8: warning: unused variable 'n' [-Wunused-variable]
   25 |     ll n=15,m=str.size();
      |        ^

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