Submission #1221565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221565		nibert	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

#include "shoes.h"
#include <vector>
#include <map>
#include <deque>
using namespace std;

// Fenwick Tree (Binary Indexed Tree) for inversion counting
struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int size) : n(size), bit(size + 2, 0) {}

    void add(int index, int val) {
        for (++index; index <= n + 1; index += index & -index)
            bit[index] += val;
    }

    int sum(int index) {
        int result = 0;
        for (++index; index > 0; index -= index & -index)
            result += bit[index];
        return result;
    }
};

// Main function required by the grader
long long count_swaps(vector<int> S) {
    int n = S.size();
    map<int, deque<int>> pos;
    vector<bool> visited(n, false);
    vector<int> target(n);
    
    // Map positions of each shoe value
    for (int i = 0; i < n; ++i)
        pos[S[i]].push_back(i);

    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        int shoe = S[i];
        int pair_index;
        
        if (shoe < 0) {
            pair_index = pos[-shoe].front();
            pos[-shoe].pop_front();
        } else {
            pair_index = pos[-shoe].front();
            pos[-shoe].pop_front();
        }

        visited[i] = visited[pair_index] = true;

        if (shoe < 0) {
            target[i] = 0;          // left shoe comes first
            target[pair_index] = 1;
        } else {
            target[pair_index] = 0; // left shoe comes first
            target[i] = 1;
        }
    }

    // Count inversions on target to determine swaps needed
    Fenwick tree(n);
    long long swaps = 0;
    for (int i = 0; i < n; ++i) {
        swaps += i - tree.sum(target[i]);
        tree.add(target[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