Submission #580524

#	Time	Username	Problem	Language	Result	Execution time	Memory
580524		haojiandan	Boarding Passes (BOI22_passes)	C++14	100 / 100	1257 ms	23500 KiB

passes

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
    if (t<0) { putchar('-'); write(-t); return; }
    if (t>9) write(t/10);
    putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int maxn=(1e5)+10;
int n,N,m;
char s[maxn],lsh[maxn];
vector<int> vec[30];
ll dp[1<<15];
vector<ll> pre[16][16],suf[16][16];
int sz[1<<15];
void output(ll ans) {
    if (ans&1) printf("%lld.5\n",ans/2);
    else printf("%lld\n",ans/2);
    exit(0);
}
int calc(int i,int x) {
    x=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin();
    return x;
}
ll S(ll x) { return x*(x+1)/2; }
int main() {
    scanf("%s",s+1); n=strlen(s+1);
    for (int i=1;i<=n;i++) lsh[++N]=s[i];
    sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
    for (int i=1;i<=n;i++) s[i]=lower_bound(lsh+1,lsh+N+1,s[i])-lsh+'A'-1;
    for (int i=1;i<=n;i++) m=max(m,s[i]-'A'),vec[s[i]-'A'].push_back(i);
    if (m==0) {
        m=n/2;
        ll ans=(ll)m*(m-1)/2+(ll)(n-m)*(n-m-1)/2;
        output(ans);
    }
    m++;
    for (int t=0;t<(1<<m);t++) {
        for (int i=0;i<m;i++) if (t>>i&1) sz[t]+=(int)vec[i].size();
        dp[t]=INF;
    }
    for (int j=0;j<m;j++) for (int i=0;i<m;i++) if (i!=j) {
        int n1=0; ll n2=0; int pos=0;
        pre[j][i].resize(vec[i].size());
        suf[j][i].resize(vec[i].size());
        for (int x=1;x<=n;x++) {
            if (j==s[x]-'A') n1++;
            if (i==s[x]-'A') n2+=n1,pre[j][i][pos]=n2,pos++;
        }
        n1=0,n2=0;
        for (int x=n;x>=1;x--) {
            if (j==s[x]-'A') n1++;
            if (i==s[x]-'A') n2+=n1,pos--,suf[j][i][pos]=n2;
        }
    }
    dp[0]=0;
    for (int t=0;t<(1<<m);t++) {
        for (int i=0;i<m;i++) if (!(t>>i&1)) {
            ll all=sz[t]*2+sz[1<<i]-1;
            ll tmp=0;
            int l=0,r=(int)vec[i].size()-1,mid,res=-1;
            while (l<=r) {
                mid=(l+r)>>1;
                int x=vec[i][mid];
                int zuo=mid;
                for (int j=0;j<m;j++) if (t>>j&1) zuo+=2*calc(j,x);
                int you=all-zuo;
                if (zuo<=you) res=mid,l=mid+1; else r=mid-1;
            }
            if (res>=0) { for (int j=0;j<m;j++) if (t>>j&1) tmp+=2*pre[j][i][res]; tmp+=S(res); }
            if (res<(int)vec[i].size()-1) { for (int j=0;j<m;j++) if (t>>j&1) tmp+=2*suf[j][i][res+1]; tmp+=S((int)vec[i].size()-res-2); }
            //for (int &x : vec[i]) tmp+=min(pre[t][x]*2+pre[1<<i][x-1],suf[t][x]*2+suf[1<<i][x+1]);
            dp[t^(1<<i)]=min(dp[t^(1<<i)],dp[t]+tmp);
        }
    }
    output(dp[(1<<m)-1]);
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
 
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
   
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
   
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%s",s+1); n=strlen(s+1);
      |     ~~~~~^~~~~~~~~~

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