Submission #1263745

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

shoes

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

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

    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=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();
        }

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

        swaps+=next-now-1;

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

    return swaps;
}

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