Submission #143344

#	Time	Username	Problem	Language	Result	Execution time	Memory
143344		pzdba	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	108 ms	15352 KiB

shoes

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

vector<int> s[200001];
int j[200001];
bool vis[200001];
int p[200001];

int ft[200001];
void update(int i, int v){
    for(;i<=200000;i+=(i&-i)) ft[i] += v;
}
int query(int i){
    int ans = 0;
    for(;i>0;i-=(i&-i)) ans+=ft[i];
    return ans;
}

long long count_swaps(vector<int> S){
    int n = S.size()/2;
    for(int i=0;i<n+n;i++){
        if(S[i] < 0) S[i] = -S[i];
        else S[i] += n;
        s[S[i]].push_back(i);
        p[i] = -1;
    }

    for(int i=0;i<n+n;i++){
        if(vis[i]) continue;
        vis[i] = 1;

        if(S[i] > n){
            int l = S[i]-n;
            int r = S[i];
            p[i] = s[l][j[l]];
            vis[p[i]] = 1;
            j[l]++;
            j[r]++;
        }
        else{
            int l = S[i];
            int r = S[i]+n;
            p[i] = s[r][j[r]];
            vis[p[i]] = 1;
            j[r]++;
            j[l]++;
        }
    }
    long long ans = 0;
    for(int i=0;i<n+n;i++){
        if(p[i] == -1) continue;
        int l = i, r = p[i];
        int l2 = l + query(200000) - query(l);
        int r2 = r + query(200000) - query(r);
        ans += r2-l2-1;
        if(S[i] > n) ans++;
        update(r, 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