# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1224952 | im2xtreme | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <cmath>
#include "shoes.h"
using namespace std;
int64_t count_swaps(vector<int> S) {
int64_t swaps = 0;
int n = S.size();
for (int i = 0; i < n; ++i) {
if (S[i] < 0) continue; // Skip right shoes
// S[i] is a left shoe
int size = S[i];
// Find matching right shoe -size
int j = i + 1;
while (j < n && S[j] != -size) ++j;
// Now move S[j] to position i+1 via adjacent swaps
while (j > i + 1) {
swap(S[j], S[j - 1]);
swaps++;
j--;
}
// i+1 now contains the right shoe
// Skip next index as it's already a valid pair
i++;
}
return swaps;
}