Submission #1224117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224117		alexaaa	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	2 ms	4936 KiB

shoes

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

set<int> wrong_pos;
vector<vector<int>> positive(100001);
vector<vector<int>> negative(100001);
void create_adj(vector<int> &S){
    for(int i = 0; i < S.size(); i++){
        if(i % 2 == 0 && S[i] < 0){
            if(S[i+1] == abs(S[i])){
            }
            else{
                wrong_pos.insert(abs(S[i]));
                negative[abs(S[i])].push_back(i);
            }
        }
        else if(i%2 == 0 && S[i] > 0){
            wrong_pos.insert(abs(S[i]));
            positive[abs(S[i])].push_back(i);
        }
        else if(i % 2 != 0 && S[i] > 0){
            if(S[i-1] < 0 && abs(S[i-1]) == S[i]){
            }
            else{
                wrong_pos.insert(abs(S[i]));
                positive[abs(S[i])].push_back(i);
            }
        }
        else if(i % 2 != 0 && S[i] < 0){
            wrong_pos.insert(abs(S[i]));
            negative[abs(S[i])].push_back(i);
        }
    }
    
    
}
int count_swaps(vector<int> S){
    create_adj(S);
    int swaps = 0;
    for(auto err:wrong_pos){
        for(int i = 0; i < positive[err].size(); i ++){
            if(positive[err][i] < negative[err][i]){
                swaps += abs(negative[err][i]-positive[err][i]);

                
            }
            else{
                swaps += abs(negative[err][i]-positive[err][i])-1;
            }

        }
    }
   
    
    return swaps;

}

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