oj.uz

Submission #846008

# Submission time Handle Problem Language Result Execution time Memory
846008 2023-09-07T05:30:23 Z damwuan Boarding Passes (BOI22_passes) C++17
55 / 100
 77 ms 5780 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,a[maxn],cost[(1<<15)+2][16],dp[(1<<15)+2],id[16],g=-1,pre[16][maxn],suf[16][maxn];
vector<int> L[16];
string s;
void sol()
{
    cin >> s;
    n=s.size();
    s=' '+s;
    for1(i,0,15) id[i]=-1;
    for1(i,1,n)
    {
        if (id[s[i]-'A']==-1)
        {
            id[s[i]-'A']=++g;
        }
        L[id[s[i]-'A']].pb(i);
        a[i]=id[s[i]-'A'];
        //cerr<< a[i]<<'\n';
    }
    g++;
    for1(i,1,n)
    {
        for1(j,0,g-1)
        {
            pre[j][i]=pre[j][i-1]+((a[i]==j)?1:0);
        }
    }
    for2(i,n,1)
    {
        for1(j,0,g-1)
        {
            suf[j][i]=suf[j][i+1]+((a[i]==j)?1:0);
        }
    }
    for1(i,0,g-1)
    {
        int k1=L[i].size()/2;
        int k2=L[i].size()-k1;
        cost[0][i]=(k1*(k1-1)+k2*(k2-1))/2;
    }
    for1(mask,1,(1<<g)-1)
    {
        for1(i,0,g-1)
        {
            int dem=0,tt=L[i].size();
            if (!((mask>>i)&1))
            {
                for2(k,tt-1,0)
                {
                    for1(j,0,g-1)
                    {
                        if ((mask>>j)&1)
                        {
                            dem+=suf[j][L[i][k]];
                        }
                    }
                }

                cost[mask][i]=dem*2+tt*(tt-1)/2;
//                if (mask==2 && i==0)
//                {
//                    cout <<cost[mask][i]<< " wtf\n";
//                }
                for1(k,0,tt-1)
                {
                    for1(j,0,g-1)
                    {
                        if ((mask>>j)&1)
                        {
                            dem+=pre[j][L[i][k]];
                            dem-=suf[j][L[i][k]];
                        }
                    }
                    cost[mask][i]=min(cost[mask][i],dem*2+(k+1)*k/2 + (tt-k-1)*(tt-k-2)/2);
                }
            }
        }
    }
    //bitset<4> xxx(2);
    //cout << xxx<<'\n';
    //cout << cost[2][0];
    for1(mask,0,(1<<g)-1) dp[mask]=inf;
    dp[0]=0;
    for1(mask,0,(1<<g)-1)
    {
        for1(i,0,g-1)
        {
            if (!((mask>>i)&1))
            {
                dp[mask^(1<<i)]=min(dp[mask^(1<<i)],dp[mask]+cost[mask][i]);
            }
        }
//        dbg(mask);
//        cout<<' '<<dp[mask]<<'\n';
    }
    //cerr<< g<<'\n';
    cout << dp[(1<<g)-1]/2;
    if (dp[(1<<g)-1]&1) cout << ".5";



}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("GROUPDIV.inp","r",stdin);
//    freopen("GROUPDIV.out","w",stdout);

    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 1
12345678
?11
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5780 KB 1st numbers differ - expected: '772893586.0000000000', found: '-300848238.0000000000', error = '1.3892492362'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 2396 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 2392 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2648 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2648 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 74 ms 3500 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 73 ms 3416 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 75 ms 3416 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 73 ms 3416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 75 ms 3416 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 77 ms 3672 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 73 ms 3416 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 72 ms 3416 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 73 ms 3416 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 73 ms 3488 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5780 KB 1st numbers differ - expected: '772893586.0000000000', found: '-300848238.0000000000', error = '1.3892492362'
7 Halted 0 ms 0 KB -