Submission #1263758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263758		piolk	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1097 ms	21320 KiB

shoes

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

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

    vector<bool> skip(n);
    vector<int> newPos(n);
    iota(newPos.begin(),newPos.end(),1);
    vector<pair<priority_queue<int,vector<int>,greater<>>,priority_queue<int,vector<int>,greater<>>>> pqs(n+1);

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

    int64_t swaps=0;

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

        int now=newPos[i];
        int next;

        if (S[i]>0){
            //szukam w ujemnych na .second
            next=pqs[S[i]].second.top();
            pqs[S[i]].second.pop();

            pqs[S[i]].first.pop(); //usuwamy now
        } else {
            //szukam w dodatnich na .first
            next=pqs[S[i]*-1].first.top();
            pqs[S[i]*-1].first.pop();

            pqs[S[i]*-1].second.pop();//usuwamy now
        }

        for (int j=i+1;j<next;j++){
            newPos[j]++;
        }

        skip[i]=true;
        skip[next]=true;

        next=newPos[next];

        swaps+=next-now-1;

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

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