Submission #153122

#	Time	Username	Problem	Language	Result	Execution time	Memory
153122		errorgorn	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	78 ms	7176 KiB

shoes

#include "shoes.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
long long s;
vector<ii> pos;
vector<ii> neg;
vector<ii> pairs;
int fen[200005]; ///pos of everything
void upd(int i,int j){
    while (i<=200005){
        fen[i]+=j;
        i+=i&-i;
    }
}
int query(int i){
    int ans=0;
    while (i){
        ans+=fen[i];
        i^=i&-i;
    }
    return ans;
}
long long count_swaps(std::vector<int> shoes) {
    s=shoes.size();
    for (int x=1;x<=s;x++){
        fen[x]=1<<(__builtin_ctz(x));
        if (shoes[x-1]<0) neg.push_back(ii(-shoes[x-1],x));
        else pos.push_back(ii(shoes[x-1],x));
    }
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end());
    int a,b;
    long long ans=0;
    s>>=1;
    for (int x=0;x<s;x++){
        a=neg[x].second;
        b=pos[x].second;
        if (a>b) swap(a,b),ans++;
        pairs.push_back(ii(a,b));
    }
    sort(pairs.begin(),pairs.end());
    for (int x=0;x<s;x++){
        a=pairs[x].first,b=pairs[x].second;
        ans+=query(b)-query(a)-1;
        upd(a,1);
        upd(b,-1);
    }
    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