Submission #1140208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140208		imarn	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	20808 KiB

shoes

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=2e5+5;
ll fw[mxn]{0};
void add(int i,int amt){
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
int qr(int i,int rs=0){
    for(;i;i-=i&-i)rs+=fw[i];
    return rs;
}priority_queue<int,vector<int>,greater<int>>v[mxn],vv[mxn];
long long count_swaps(std::vector<int> s){
    int n=s.size();ll ans=0;
    for(int i=0;i<n;i++){
        if(s[i]>0)v[s[i]].push(i);
        if(s[i]<0)vv[-s[i]].push(i);
    }int cnt=n/2;
    while(cnt--){
        int rs=1e9,ml=-1,mr=-1,mm=-1;
        for(int i=1;i<n;i++){
            if(v[i].empty())continue;
            int x=v[i].top(),y=vv[i].top();
            int tx=x+qr(x+1),ty=y+qr(y+1);
            if(tx>ty&&rs>abs(tx-1)+abs(ty)){
                rs=abs(tx-1)+abs(ty);
                ml=min(x,y)+1,mr=max(x,y)+2;
                mm=i;
            }
            if(tx<ty&&rs>abs(tx)+abs(ty)){
                rs=abs(tx)+abs(ty);
                ml=min(x,y)+1,mr=max(x,y)+2;
                mm=i;
            }
        }ans+=rs;add(ml,-1);add(mr,-1);v[mm].pop();vv[mm].pop();
    }return ans;
}

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