Submission #1029342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029342		baldwinhuang1	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	37 ms	4412 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
 
long long count_swaps(vector<int> s) {
    int n = s.size()/2;
    priority_queue<int> L, R;
    
    for (int i = 0; i < 2*n; i++) {
        if (s[i] < 0) {
            L.push(-i);
        } else {
            R.push(-i);
        }
    }
    long long swaps = 0;
    for (int i = 0; i < 2*n; i++) {
        if (s[i] < 0) {
            // L
            if (i % 2 == 1) {
                // Mismatch
                int nearest = -R.top();
                R.pop();
                swaps += nearest-i;
                if (!L.empty()) L.pop();
                L.push(-nearest);
                s[i] *= -1; s[nearest] *= -1;
                //cout << 1 << " " << nearest << " " << i << '\n';
            } else if (!L.empty()) {
                // Correcto
                L.pop();
            }
        } else {
            // R
            if (i % 2 == 0) {
                // Mismatch
                int nearest = -L.top();
                L.pop();
                swaps += nearest - i;
                if (!R.empty()) R.pop();
                R.push(-nearest);
                s[i] *= -1; s[nearest] *= -1;
                //cout << nearest << " " << i << '\n';
            } else if (!R.empty()) {
                // Correcto
                R.pop();
            }
        }
    }
 
    return swaps;
}

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