Submission #202344

#	Time	Username	Problem	Language	Result	Execution time	Memory
202344		a_player	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	121 ms	135032 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+1;

deque<int> d[2*MAXN];
bitset<2*MAXN> v;
int ft[2*MAXN];
int N;
void update(int k,int val){
    int x=k+1;
    while(x<=N){
        ft[x]+=val;
        x+=x&(-x);
    }
}
int query(int k){
    int x=k+1;
    int s=0;
    while(x>0){
        s+=ft[x];
        x-=x&(-x);
    }
    return s;
}

long long count_swaps(vector<int> s) {
     N=s.size();
    long long ans=0;
	for(int i=0;i<N;i++)d[s[i]+MAXN].push_back(i);
    for(int i=0;i<N;i++){
        if(v[i])continue;
        d[s[i]+MAXN].pop_front();
        int h=d[MAXN-s[i]].front();
        d[MAXN-s[i]].pop_front();
        v[i]=1;
        v[h]=1;
        ans+=query(h)-query(i);
        update(i,2);
        update(h,-1);
        if(s[i]>s[h])ans++;
    }
    return ans;
}

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