oj.uz

Submission #739257

# Submission time Handle Problem Language Result Execution time Memory
739257 2023-05-10T09:08:59 Z edogawa_something Boarding Passes (BOI22_passes) C++17
60 / 100
 1757 ms 17156 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define test1 ll qqqqq=1;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(int i=0;i<n;i++)
#define forx(i,j,n) for(int i=j;i<n;i++)
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
#define duration chrono::duration_cast<chrono::milliseconds>(end-start)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const ll dx[]{1,0,-1,0,1,-1,1,-1};
const ll dy[]{0,-1,0,1,1,-1,-1,1};
const ll inf=1e18;
const ll mod=1e9+7;
const ll LM=1e8+1;
const ll M=2e7+10;
const ll MM=2002;
const ll MMM=501;
const ld pi=acos(-1);
//const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  r%=m;
  while(to){
    if((to&1)){
      res*=r,res%=m;
    }
    r*=r,r%=m;
    to=(to>>1);
  }
  return res;
}
ld n,dp[M];
ll cnt[20];
string s;
bl mp[M];
int main(){
  fast
  //freopen("gen.txt","r",stdin);
  auto start=measure;
  test1{
    cin>>s;
    for(auto it:s){
      cnt[it-'A']++;
    }
    n=s.size();
    forn(i,(1<<20))
    dp[i]=n*n*n;
    dp[0]=0; 
    forn(i,(1<<10)){
      ll cc=0;
      forn(j,n){
        if(((1<<(s[j]-'A'))&i))
        mp[j]=1;
        else
        mp[j]=0;
        cc+=mp[j];
      }
      forn(bit,10){
        ld res=0;
        if(((1<<bit)&i)==0){
          ll c=0;
          ll ccc=0;
          forn(j,n){
            if(ll(s[j])==bit+'A')
            res+=min(ld(c)/ld(2)+ld(ccc),(ld(cnt[bit]-c-1)/ld(2))+ld(cc)-ld(ccc));
            ccc+=mp[j];
            c+=bl(ll(s[j])==(bit+'A'));
          }
          dp[(i|(1<<bit))]=min(dp[(i|(1<<bit))],dp[i]+res);
        }
      }
    }
    cout<<fixed<<dp[(1<<10)-1]<<'\n';
  }
  auto end=measure;
  auto dur=duration;
  //cout<<fixed<<dur.count()<<'\n';
  return 0;
}
/*
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 9 ms 16724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 9 ms 16724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 30 ms 16724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1384 ms 17084 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1632 ms 17128 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1735 ms 17156 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1757 ms 17148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 11 ms 16728 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 16756 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 16724 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 16724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 9 ms 16680 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 16724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 10 ms 16716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 10 ms 16748 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 9 ms 16708 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 16724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 16680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 16700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 16692 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 16772 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 16724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 11 ms 16712 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 11 ms 16728 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 16756 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 11 ms 16724 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 11 ms 16724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 9 ms 16680 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 11 ms 16724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 10 ms 16716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 10 ms 16748 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 9 ms 16708 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 16724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 16680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 10 ms 16700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 16692 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 10 ms 16772 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 10 ms 16724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 11 ms 16712 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 9 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 11 ms 16708 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 11 ms 16724 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 11 ms 16724 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 11 ms 16728 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 10 ms 16724 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 11 ms 16724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 10 ms 16680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 9 ms 16724 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 9 ms 16724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 9 ms 16756 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 10 ms 16724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 10 ms 16728 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 10 ms 16724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 10 ms 16716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 9 ms 16724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 9 ms 16724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 189 ms 16768 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 183 ms 16788 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 226 ms 16772 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 204 ms 16776 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 189 ms 16772 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 186 ms 16724 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 186 ms 16772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 193 ms 16772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 201 ms 16772 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 199 ms 16772 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 188 ms 16780 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 187 ms 16768 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 9 ms 16724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 9 ms 16724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 30 ms 16724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1384 ms 17084 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1632 ms 17128 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1735 ms 17156 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1757 ms 17148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 9 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 11 ms 16728 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 11 ms 16756 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 11 ms 16724 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 11 ms 16724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 9 ms 16680 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 11 ms 16724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 10 ms 16716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 10 ms 16748 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 9 ms 16708 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 9 ms 16724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 9 ms 16680 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 10 ms 16700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 9 ms 16692 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 10 ms 16772 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 10 ms 16724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 11 ms 16712 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 9 ms 16724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 11 ms 16708 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 11 ms 16724 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 11 ms 16724 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 11 ms 16728 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 10 ms 16724 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 11 ms 16724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 10 ms 16680 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 9 ms 16724 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 16724 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 9 ms 16756 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 10 ms 16724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 10 ms 16728 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 10 ms 16724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 10 ms 16716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 9 ms 16724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 9 ms 16724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 189 ms 16768 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 183 ms 16788 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 226 ms 16772 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 204 ms 16776 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 189 ms 16772 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 186 ms 16724 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 186 ms 16772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 193 ms 16772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 201 ms 16772 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 199 ms 16772 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 188 ms 16780 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 187 ms 16768 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 10 ms 16716 KB 1st numbers differ - expected: '7.5000000000', found: '6.0000000000', error = '0.2000000000'
57 Halted 0 ms 0 KB -