Submission #500877

#	Time	Username	Problem	Language	Result	Execution time	Memory
500877		Khizri	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	443 ms	149792 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"OK"<<endl;
const int mxn=2e5+5;
ll color[mxn],n,tree[mxn];
ll query(int ind){
    ll ans=0;
    while(ind>0){
        ans+=tree[ind];
        ind-=(ind&(-ind));
    }
    return ans;
}
void update(int ind,int val){
    while(ind<=n){
        tree[ind]+=val;
        ind+=(ind&(-ind));
    }
}
bool f(pii a,pii b){
    return a.F+a.S<b.F+b.S;
}
ll funk(vector<pii>&vt){
    ll ans=0;
    sort(all(vt),f);
    for(int i=0;i<n/2;i++){
        ll x=vt[i].F+query(vt[i].F);
        ans+=abs(x-1);
        update(vt[i].F,-1);
        ll y=vt[i].S+query(vt[i].S);
        ans+=abs(y-1);
        update(vt[i].S,-1);
    }
    return ans;
}
long long count_swaps(vector<int> s) {
    n=s.size();
    map<int,queue<int>>mp;
	vector<pii>vt;
	for(int i=0;i<n;i++){
        if(mp[-s[i]].size()>0){
            int x=mp[-s[i]].front();
            mp[-s[i]].pop();
            if(s[i]<0){
                vt.pb({i+1,x});
            }
            else{
                vt.pb({x,i+1});
            }
        }
        else{
            mp[s[i]].push(i+1);
        }
	}
    ll ans=funk(vt);
    return ans;
}

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