Submission #1282003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282003		xorreverse	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	12720 KiB

shoes

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

vector<int> left_shoose[100005];
vector<int> right_shoose[100005];
long long count_swaps(vector<int> s){
    int n = s.size() / 2;
    for (int i = 0; i < 2 * n; i ++){
        if (s[i] < 0) left_shoose[-s[i]].push_back(i);
        else right_shoose[s[i]].push_back(i);
    }
    long long res = 0;
    for (int i = 0; i < n ; i ++){
        int meo = 1e9;
        int left_chose = 0;
        int right_chose = 0;
        for (int j = 0; j <= n; j ++){
            if (!left_shoose[j].size()) continue;
            int left_val = left_shoose[j][0];
            int right_val = right_shoose[j][0];
            int ans = right_val + left_val;
            if (right_val < left_val) ans ++;
            if (ans < meo){
                meo = ans;
                left_chose = left_val;
                right_chose = right_val;
            }
        }
        res += meo;
     //   cout << left_chose << " " << right_chose << endl;
        for (int j = 0; j <= n; j ++){
            vector<int> nw;
            for (auto e : left_shoose[j]){
                if (e == left_chose) continue;
                int meo = e;
                if (e < left_chose) meo ++;
                if (e <  right_chose) meo++;
                nw.push_back(meo);
            }
            swap(left_shoose[j], nw);
            nw.clear();
            for (auto e : right_shoose[j]){
                if (e == right_chose) continue;
                int meo = e;
                if (e < left_chose) meo ++;
                if (e < right_chose) meo ++;
                nw.push_back(meo);
            }
            swap(right_shoose[j], nw);
            nw.clear();
        }

        res -= 2 * i;
        res -= 2 * i + 1;
       // cout << res << endl;
    }
    return res;
}

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