제출 #1290803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290803		lucasdmy	Arranging Shoes (IOI19_shoes)	C++20	30 / 100	1096 ms	15592 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;
    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]);
        }
    }
    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]);
        }
    }
    reverse(left2.begin(), left2.end());
    reverse(left4.begin(), left4.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++;
        }
    }
    return min(resp, 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);
}*/

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