제출 #1323989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323989		sh_qaxxorov_571	Arranging Shoes (IOI19_shoes)	C++20	15 / 100	201 ms	273628 KiB

shoes

#include <vector>
#include <queue>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void update(int i, int val) {
        for (++i; i <= n; i += i & -i) tree[i] += val;
    }
    int query(int i) {
        int res = 0;
        for (++i; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
};
ll count_swaps(vector<int> s) {
    int n = s.size();
    int pairs = n / 2;
    vector<queue<int>> pos_p(n + 1), pos_n(n + 1);
    for (int i = 0; i < n; i++) {
        if (s[i] > 0) pos_p[s[i]].push(i);
        else pos_n[-s[i]].push(i);
    }
    vector<int> target(n);
    vector<bool> visited(n, false);
    BIT bit(n);
    for (int i = 0; i < n; i++) bit.update(i, 1);
    ll total_swaps = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        int size = abs(s[i]);
        int l_idx, r_idx;
        if (s[i] < 0) {
            l_idx = i;
            r_idx = pos_p[size].front();
            pos_p[size].pop();
            pos_n[size].pop();
        } else { 
            r_idx = i;
            l_idx = pos_n[size].front();
            pos_n[size].pop();
            pos_p[size].pop();
            total_swaps++;
        }
        visited[l_idx] = visited[r_idx] = true;
        int current_l_pos = i + bit.query(l_idx - 1) - l_idx; 
        int current_r_pos = r_idx + bit.query(r_idx - 1) - r_idx;
        total_swaps += (current_r_pos - current_l_pos - 1);
        bit.update(l_idx, -1);
        bit.update(r_idx, -1);
    }
    return total_swaps;
}

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