oj.uz

Submission #685554

# Submission time Handle Problem Language Result Execution time Memory
685554 2023-01-24T14:20:26 Z MtSaka Boarding Passes (BOI22_passes) C++17
25 / 100
 3 ms 2900 KB 
#include<bits/stdc++.h>
using ll=long long;
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
using namespace std;
int main(){
  string S;cin>>S;
  vector<int>s;
  for(auto&e:S)s.push_back(e-'A');
  const int n=s.size();
  const int g=*max_element(s.begin(),s.end())+1;
  vector idx(g,vector<int>());
  rep(i,0,n)idx[s[i]].push_back(i);
  vector prefix(g,vector<ll>(n,0));
  auto suffix=prefix;
  vector suml(g,vector<ll>(n,0));
  auto sumr=suml;
  rep(i,0,n){
    prefix[s[i]][i]++;
    suffix[s[i]][i]++;
  }
  rep(i,0,g){
    rep(j,0,n-1)prefix[i][j+1]+=prefix[i][j];
    rrep(j,0,n-1)suffix[i][j]+=suffix[i][j+1];
  }
  vector<int>last(g,-1);
  rep(i,0,n){
    rep(j,0,g)suml[j][i]=prefix[j][i];
    if(last[s[i]]!=-1)rep(j,0,g)suml[j][i]+=suml[j][last[s[i]]];
    last[s[i]]=i;
  }
  last=vector<int>(g,-1);
  rrep(i,0,n){
    rep(j,0,g)sumr[j][i]=suffix[j][i];
    if(last[s[i]]!=-1)rep(j,0,g)sumr[j][i]+=sumr[j][last[s[i]]];
    last[s[i]]=i;
  }
  auto calc1=[&](ll bit,ll i)->int {
    int ok=-1,ng=idx[i].size();
    while(ng-ok>1){
      int mid=(ok+ng)>>1;
      int p=idx[i][mid];
      ll l=0,r=0;
      rep(j,0,g){
        if((bit>>j)&1)l+=prefix[j][p]*2,r+=suffix[j][p]*2;
        else if(i==j)l+=prefix[j][p],r+=suffix[j][p];
      }
      if(l<=r)ok=mid;
      else ng=mid;
    }
    return ok;
  };
  auto calc2=[&](ll bit,ll i,int m)->ll {
    ll ret=0;
    if(m!=-1){
      int p=idx[i][m];
      rep(j,0,g){
        if((bit>>j)&1)ret+=suml[j][p]*2;
      }
    }
    if(m!=(int)idx[i].size()-1){
      int p=idx[i][m+1];
      rep(j,0,g){
        if((bit>>j)&1)ret+=sumr[j][p]*2;
      }
    }
    ret+=m*(m+1)/2;
    ret+=(idx[i].size()-m-1)*(idx[i].size()-m-2)/2;
    return ret;
  };
  vector dp(1<<g,LLONG_MAX>>2);
  dp[0]=0;
  rep(bit,0,1<<g){
    rep(i,0,g){
      if((bit>>i)&1)continue;
      if(idx[i].empty())dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]);
      else{
        int m=calc1(bit,i);
        ll cost=calc2(bit,i,m);
         //cerr<<bit<<" "<<i<<" "<<m<<" "<<cost<<endl;
        dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]+cost);
      }
    }
  }
  //for(auto&i:dp)cerr<<i<<endl;
  cout<<dp.back()/2.0<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 304 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 300 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 296 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 304 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 300 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 296 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 300 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 304 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 300 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 300 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 300 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 300 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 3 ms 2900 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 3 ms 2868 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -