Submission #1281949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281949		xorreverse	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1096 ms	4124 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

long long count_swaps(vector<int> s){
    int n = s.size();
    vector<pair<int, int>> left_shoose;
    vector<pair<int, int>> right_shoose;
    for (int i = 0; i < n; i ++){
        if (s[i] < 0) left_shoose.push_back({-s[i], i});
        else right_shoose.push_back({s[i], i});
    }
    long long res = 0;
    for (int i = 0; i < n / 2; i ++){
        pair<int, int> left_val = left_shoose[0];
        res += left_val.second - 2 * i;
        for (int j = 0; j < right_shoose.size(); j ++){
            if (right_shoose[j].second < left_val.second){
                right_shoose[j].second ++;
            }
            else break;
        }
        left_shoose.erase(left_shoose.begin());

        //cout << "wat the sigma " << res << " " << left_val.second << " " << 2 * i << " " << right_shoose[0].second<< endl;
        pair<int, int> right_val;
        int sigma = 0;
        for (int j = 0; j < right_shoose.size(); j ++){
            if (right_shoose[j].first == left_val.first){
                right_val = right_shoose[j];
                sigma = j;
                break;
            }
            else right_shoose[j].second ++;
        }
        res += right_val.second - (2 * i + 1);
        for (int j = 0; j < left_shoose.size(); j ++){
            if (left_shoose[j].second < right_val.second){
                left_shoose[j].second ++;
            }
            else break;
        }
        right_shoose.erase(right_shoose.begin() + sigma);
        //cout << "mao fuq " << res << endl;
    }
    return res;
}

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