Submission #1290804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290804		lucasdmy	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	1 ms	332 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, left2, left3, left4, left5, left6;
    map<int, int>freq, freq2;
    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]));
        }
        if(v[k]<0){
            left3.push_back(-v[k]);
        }else{
            left5.push_back(v[k]);
        }
    }
    for(int k=v.size()-1;k>=0;k--){
        freq2[abs(v[k])]++;
        if(freq2[abs(v[k])]%2==1){
            left2.push_back(abs(v[k]));
        }
        if(v[k]<0){
            left4.push_back(-v[k]);
        }else{
            left6.push_back(v[k]);
        }
    }
    reverse(left2.begin(), left2.end());
    reverse(left4.begin(), left4.end());
    reverse(left6.begin(), left6.end());
    vector<int>per(left.size());
    for(int k=0;k<left.size();k++){
        per[k]=k;
    }
    long long int resp=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]);
            resp++;
        }
    }
    vector<int>v3=v;
    long long int aux=0;
    for(int k=0;k<v3.size();k++){
        int ex;
        if(k%2==0){
            ex=-left2[per[k/2]];
        }else{
            ex=left2[per[k/2]];
        }
        int f=k;
        while(v3[f]!=ex){
            f++;
        }
        for(int i=f;i>k;i--){
            swap(v3[i], v3[i-1]);
            aux++;
        }
    }
    resp=min(resp, aux);
    v3=v;
    aux=0;
    for(int k=0;k<v3.size();k++){
        int ex;
        if(k%2==0){
            ex=-left3[per[k/2]];
        }else{
            ex=left3[per[k/2]];
        }
        int f=k;
        while(v3[f]!=ex){
            f++;
        }
        for(int i=f;i>k;i--){
            swap(v3[i], v3[i-1]);
            aux++;
        }
    }
    resp=min(resp, aux);
    v3=v;
    aux=0;
    for(int k=0;k<v3.size();k++){
        int ex;
        if(k%2==0){
            ex=-left4[per[k/2]];
        }else{
            ex=left4[per[k/2]];
        }
        int f=k;
        while(v3[f]!=ex){
            f++;
        }
        for(int i=f;i>k;i--){
            swap(v3[i], v3[i-1]);
            aux++;
        }
    }
    resp=min(resp, aux);
    v3=v;
    aux=0;
    for(int k=0;k<v3.size();k++){
        int ex;
        if(k%2==0){
            ex=-left5[per[k/2]];
        }else{
            ex=left5[per[k/2]];
        }
        int f=k;
        while(v3[f]!=ex){
            f++;
        }
        for(int i=f;i>k;i--){
            swap(v3[i], v3[i-1]);
            aux++;
        }
    }
    resp=min(resp, aux);
    v3=v;
    aux=0;
    for(int k=0;k<v3.size();k++){
        int ex;
        if(k%2==0){
            ex=-left6[per[k/2]];
        }else{
            ex=left6[per[k/2]];
        }
        int f=k;
        while(v3[f]!=ex){
            f++;
        }
        for(int i=f;i>k;i--){
            swap(v3[i], v3[i-1]);
            aux++;
        }
    }
}
/*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);
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:148:1: warning: no return statement in function returning non-void [-Wreturn-type]
  148 | }
      | ^

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