Submission #1226892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226892		alexaaa	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	4 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);
vector<pair<int,int>> invalids;
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);
                invalids.push_back({i,negative[abs(S[i])].size()-1});
            }
        }
        else if(i%2 == 0 && S[i] > 0){
            wrong_pos.insert(abs(S[i]));
            positive[abs(S[i])].push_back(i);
            invalids.push_back({i,positive[abs(S[i])].size()-1});
        }
        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);
                invalids.push_back({i,positive[abs(S[i])].size()-1});
            }
        }
        else if(i % 2 != 0 && S[i] < 0){
            wrong_pos.insert(abs(S[i]));
            negative[abs(S[i])].push_back(i);
            invalids.push_back({i,negative[abs(S[i])].size()-1});
        }
    }
   
    
}
long long count_swaps(vector<int> S){
    create_adj(S);
    long long swaps = 0;
    long long calculation;

    for(auto err:wrong_pos){
        for(int i = 0; i < negative[err].size(); i ++){
            if(positive[err][i] < negative[err][i]){
                calculation = abs(positive[err][i]-negative[err][i]);
                
                

                swaps += calculation ;

                for(int j = positive[err][i]+1; j < negative[err][i]; j++){
                    int index = invalids[j].first;
                    int num = S[index];
                    if(num < 0){
                        negative[abs(num)][invalids[j].second] --;
                    }
                    else{
                        positive[num][invalids[j].second] --;

                    }

                }


                
            }
            else{
                calculation = (abs(positive[err][i]-negative[err][i])-1);
                if(calculation == 0){
                    continue;
                }

                swaps += calculation ;
                for(int j = positive[err][i]-1; j > negative[err][i]; j--){
                    int index = invalids[j].first;
                    int num = S[index];
                    if(num < 0){
                        negative[abs(num)][invalids[j].second] ++;
                    }
                    else{
                        positive[num][invalids[j].second] ++;

                    }

                }
            }

        }
    }
   
    
    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