Submission #760521

#	Time	Username	Problem	Language	Result	Execution time	Memory
760521		alexander707070	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	121 ms	139768 KiB

shoes

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int to[MAXN],perm[MAXN],n,t;
int fenwick[MAXN];
long long ans;

queue<int> q[MAXN];

void update(int x){
    while(x<=n){
        fenwick[x]++;
        x+=(x & (-x));
    }
}

int getsum(int x){
    int res=0;
    while(x>=1){
        res+=fenwick[x];
        x-=(x & (-x));
    }
    return res;
}

long long count_swaps(vector<int> S){
    n=int(S.size());

    t=1;
    for(int i=1;i<=n;i++){
        if(S[i-1]<0 and !q[-S[i-1]+n/2].empty()){
            perm[q[-S[i-1]+n/2].front()]=t+1; perm[i]=t;
            q[-S[i-1]+n/2].pop(); t+=2;
        }else if(S[i-1]<0)q[-S[i-1]].push(i);

        if(S[i-1]>0 and !q[S[i-1]].empty()){
            perm[q[S[i-1]].front()]=t; perm[i]=t+1;
            q[S[i-1]].pop(); t+=2;
        }else if(S[i-1]>0)q[S[i-1]+n/2].push(i);
    }

    for(int i=1;i<=n;i++){
        ans+=getsum(n)-getsum(perm[i]);
        update(perm[i]);
    }

    return ans;
}

/*
int main(){
    cout<<count_swaps({-2, 2, 2, -2, -2, 2})<<"\n";

}
*/

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