Submission #1263752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263752		piolk	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	2632 KiB

shoes

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

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

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

    int64_t swaps=0;

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

        for (int j=i+1;j<n;j++){
            if (skip[j]) continue;
            if (S[j]==S[i]*-1){
                posNext=newPos[j];
                skip[j]=true;
                break;
            }
            newPos[j]++;
        }

        skip[i]=true;

        swaps+=posNext-posNow-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