Submission #1263750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263750		piolk	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

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

vector<int> tree;
int len=0;

void treeUpdate(int v,int currStart,int currEnd,int lookStart,int lookEnd){
    if (currStart>=lookStart && currEnd<=lookEnd){
        tree[v]++;
        return;
    }

    if (currStart>lookEnd || currEnd<lookStart) return;

    int mid=(currStart+currEnd)/2;
    treeUpdate(2*v,currStart,mid,lookStart,lookEnd);
    treeUpdate(2*v,mid+1,currEnd,lookStart,lookEnd);
}

int treeGet(int pos){
    pos+=len;
    int ans=tree[pos];

    while (pos>1){
        pos/=2;
        ans+=tree[pos];
    }
    return ans;
}

int64_t count_swaps(vector<int> S){
    tree.clear();
    int n=S.size();

    for (int i=1;i<=21;i++){
        int p=(1<<i);
        if (p>=n){
            len=p;
            break;
        }
    }

    tree.resize(2*len);
    for (int i=0;i<n;i++) tree[i+len]=i;

    int swaps=0;

    vector<pair<priority_queue<int,vector<int>,greater<>>,priority_queue<int,vector<int>,greater<>>>> pqs(n+1);

    vector<bool> skip(n+1);

    for (int i=0;i<n;i++){
        if (S[i]<0){
            //.first
            
            pqs[S[i]*-1].first.push(i);
        } else {
            //.second

            pqs[S[i]].second.push(i);
        }
    }

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

        int now=treeGet(i);
        int next;
        if (S[i]<0){
            next=pqs[S[i]*-1].second.top();
            pqs[S[i]*-1].second.pop();

            pqs[S[i]*-1].first.pop();
        } else {
            next=pqs[S[i]].first.top();
            pqs[S[i]].first.pop();

            pqs[S[i]].second.pop();
        }

        next=treeGet(next);

        cout<<now<<" "<<next<<"\n";

        skip[now]=true;
        skip[next]=true;

        swaps+=next-now-1;

        if (S[i]>0) swaps++;

        treeUpdate(1,0,len-1,0,next-1);
    }

    return swaps;
}

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