Submission #1021775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021775		nisanduu	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	192 ms	40784 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void update(vector<ll>&seg,ll ind,ll l,ll r,ll givenpos){
    if(l==r){
        seg[ind]+=1;
        return;
    }
    ll mid = l + (r-l)/2;
    if(mid>=givenpos){
        update(seg,2*ind+1,l,mid,givenpos);
    }else{
        update(seg,2*ind+2,mid+1,r,givenpos);
    }
    seg[ind] = seg[2*ind+1] + seg[2*ind+2];
    return;
}

ll query(vector<ll>&seg,ll ind,ll l,ll r,ll left,ll right){
    if(l>right||r<left) return 0;
    if(left<=l&&right>=r) return seg[ind];
    ll mid = l + (r-l)/2;
    return query(seg,2*ind+1,l,mid,left,right) + query(seg,2*ind+2,mid+1,r,left,right);
}

long long count_swaps(std::vector<int> s) {
    long long ans = 0;
    long long n = s.size();
    vector<vector<ll>> left(n+10),right(n+10);
    for(ll i=0;i<n;i++){
        ll sz = abs(s[i]);
        if(s[i]<0){
            left[sz].push_back(-i);
        }else{
            right[sz].push_back(-i);
        }
    }
    for(ll i=0;i<n+1;i++){
        sort(left[i].begin(),left[i].end());
        sort(right[i].begin(),right[i].end());
    }
    // for(auto indx:left[1]) cout<<indx<<endl;
    // cout<<"olo"<<endl;
    // for(auto indx:right[1]) cout<<indx<<endl;
    vector<ll> seg(6*n);
    map<ll,ll> used;
    ll cnt = 0;
    for(ll i=0;i<n;i++){
        if(!used[i]){
            ll sz = abs(s[i]);
            ll tmpA = 0;
            ll pos;
            if(s[i]<0){
                pos = right[sz].back();
            }else{
                pos = left[sz].back();
            }
            pos *= -1;
            right[sz].pop_back();
            left[sz].pop_back();
            ll am = pos - i - 1;
            
            ll q = query(seg,0,0,n-1,i,pos);
            am = am - q;
            //cout<<q<<" "<<i<<" "<<pos<<" "<<am<<endl;
            update(seg,0,0,n-1,pos);
            used[pos]=1;
            used[i]=1;
            tmpA = am;
            if(s[i]>0) tmpA++;
            ans+=tmpA;
        }
    }
     
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:49:8: warning: unused variable 'cnt' [-Wunused-variable]
   49 |     ll cnt = 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