oj.uz

Submission #846010

# Submission time Handle Problem Language Result Execution time Memory
846010 2023-09-07T05:32:45 Z damwuan Boarding Passes (BOI22_passes) C++17
55 / 100
 101 ms 5064 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=1e18;
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 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5064 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2648 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 2396 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 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 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 2396 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 2396 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 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2396 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 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2648 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 2396 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 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 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 2396 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 2396 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 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2396 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 2396 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 2396 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 2396 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2648 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 2596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2396 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 2904 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2908 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 98 ms 4408 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 90 ms 4188 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 91 ms 4472 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 87 ms 4364 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 93 ms 4184 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 93 ms 4368 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 97 ms 4364 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 97 ms 4352 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 101 ms 4432 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 92 ms 4188 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 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5064 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -