Submission #1290793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290793		lucasdmy	Arranging Shoes (IOI19_shoes)	C++20	30 / 100	1097 ms	8416 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long int count_swaps(vector<int>v){
    vector<long long int>left;
    map<int, int>freq;
    for(int k=0;k<v.size();k++){
        freq[abs(v[k])]++;
        if(freq[abs(v[k])]%2==1){
            left.push_back(abs(v[k]));
        }
    }
    vector<int>per(left.size());
    for(int k=0;k<left.size();k++){
        per[k]=k;
    }
    long long int resp=1e18;
    do{
        long long int aux=0;
        vector<int>v2=v;
        for(int k=0;k<v2.size();k++){
            int ex;
            if(k%2==0){
                ex=-left[per[k/2]];
            }else{
                ex=left[per[k/2]];
            }
            int f=k;
            while(v2[f]!=ex){
                f++;
            }
            for(int i=f;i>k;i--){
                swap(v2[i], v2[i-1]);
                aux++;
            }
        }
        resp=min(resp, aux);
    }while(next_permutation(per.begin(), per.end()));
    return resp;
}
/*int main(){
    int n;
    cin>>n;
    vector<int>v(2*n);
    for(int k=0;k<2*n;k++){
        cin>>v[k];
    }
    cout<<count_swaps(v);
}*/

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