Submission #846099

#	Time	Username	Problem	Language	Result	Execution time	Memory
846099		damwuan	Boarding Passes (BOI22_passes)	C++17	100 / 100	222 ms	54212 KiB

passes

#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=1e18;
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],prep[16][16],suff[16][16];
string s;
void dbg(int mask)
{
    bitset<5> xxx(mask);
    cout << xxx;
}
int f(int x,int k,int mask)
{
    int tt=L[k].size();
    int sum=((x-1)*x/2) + ((tt-x)*(tt-x-1)/2);
    if (x==tt)
    {
        for1(i,0,g-1)
        {
            if ((mask>>i)&1)
            {
                sum+=2*prep[k][i][tt-1];
            }
        }
        return sum;
    }
   //cerr<<k<<' '<<x<<' '<< "wtf\n";
    for1(i,0,g-1)
    {
        if ((mask>>i)&1)
        {
            sum+=2*suff[k][i][x];
            //cerr<<k<<' '<<i<<' '<<x<<suff[k][i][x]<<'\n';
        }
    }
    if (x==0)return sum;
    for1(i,0,g-1)
    {
        if ((mask>>i)&1)
        {
            sum+=2*prep[k][i][x-1];
            //cerr<<k<<' '<<i<<' '<<x<< prep[k][i][x-1]<<'\n';
        }
    }
    return sum;
}
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)
    {
        for1(j,0,g-1)
        {
            //if (i==j) continue;
            prep[i][j].resize(L[i].size()+1);
            prep[i][j][0]=pre[j][L[i][0]];
            for1(k,1,L[i].size()-1)
            {
                prep[i][j][k]=prep[i][j][k-1]+pre[j][L[i][k]];
            }

            suff[i][j].resize(L[i].size()+1);
            suff[i][j][L[i].size()-1]=suf[j][L[i][L[i].size()-1]];
            for2(k,L[i].size()-2,0)
            {
                suff[i][j][k]=suff[i][j][k+1]+suf[j][L[i][k]];
            }
        }
    }
    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))
            {
                int l=0,r=tt,mid;
                while (r-l>1)
                {
                    mid=l+r>>1;
                    if (f(mid,i,mask)<f(mid+1,i,mask))
                    {
                        r=mid;
                    }
                    else
                    {
                        l=mid;
                    }
                }
                cost[mask][i]=min(f(l,i,mask),f(l+1,i,mask));
                //if (mask==3 && i==2 ) cerr<< "adsad "<< l+1<<' '<<f(l+1,i,mask)<<' '<<f(l,i,mask)  <<'\n';
            }
        }
    }
//    cerr<< f(2,0,2)<<'\n';
////    bitset<4> xxx(2);
////    cout << xxx<<'\n';
//    cout << cost[3][2]<<'\n';
    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
*/

Compilation message (stderr)

passes.cpp: In function 'void sol()':
passes.cpp:6:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
  105 |             for1(k,1,L[i].size()-1)
      |                  ~~~~~~~~~~~~~~~~~
passes.cpp:105:13: note: in expansion of macro 'for1'
  105 |             for1(k,1,L[i].size()-1)
      |             ^~~~
passes.cpp:134:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |                     mid=l+r>>1;
      |                         ~^~
passes.cpp:128:17: warning: unused variable 'dem' [-Wunused-variable]
  128 |             int dem=0,tt=L[i].size();
      |                 ^~~

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