Submission #1272504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272504		kiteyu	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	390 ms	35620 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll=long long;
const int N=2e5;
int bit[N+5];
int b[N+5],d[N+5];
map<int,vector<int>>pos;
map<int,int>f;

int n;
void upd(int idx,int val){for(;idx<=n;idx+=(idx&-idx))bit[idx]+=val;}
int get(int idx){int res=0;for(;idx>0;idx-=(idx&-idx))res+=bit[idx];return res;}

ll count_swaps(vector<int>a){
    for(int i=1;i<=N;++i)bit[i]=0;
    n=(int)a.size();
    int n1=0;
    for(int i=1;i<=n;++i){
        int x=a[i-1];
//        cout<<x<<' '<<f[x]<<'\n';
        if(f[-x]<=f[x]){
            b[++n1]=-abs(x);
            b[++n1]=abs(x);
        }
        f[x]++;
    }
//    for(int i=1;i<=n;++i)cout<<b[i]<<' ';
//    cout<<'\n';
    for(int i=n;i>=1;--i){
        pos[b[i]].push_back(i);
    }
    for(int i=1;i<=n;++i){
        d[i]=pos[a[i-1]].back();
        pos[a[i-1]].pop_back();
        //cout<<d[i]<<' ';
    }
//    cout<<'\n';
    ll ans=0;
    for(int i=1;i<=n;++i){
        upd(d[i],1);
        ans+=(ll)i-get(d[i]);
//        cout<<ans<<" "<<get(d[i])<<'\n';
    }
    return ans;
}
//int main(){
//    freopen("task.inp","r",stdin);
//    freopen("task.out","w",stdout);
//    vector<int>v;
//    for(int x;cin>>x;){
//        v.push_back(x);
//    }
//    cout<<count_swaps(v);
//    return 0;
//}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15