제출 #1324020

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

shoes

#include "shoes.h"
#include <vector>
#include <cmath>
#include <deque>
#include <algorithm>

using namespace std;

typedef long long ll;

// Fenwick Tree (Binary Indexed Tree) inversiyalarni sanash uchun
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void update(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

ll count_swaps(vector<int> s) {
    int n = s.size();
    int pairs = n / 2;
    
    // Har bir o'lchamdagi poyabzal manzillarini saqlaymiz
    vector<deque<int>> pos_left(n + 1), pos_right(n + 1);
    for (int i = 0; i < n; i++) {
        if (s[i] < 0) pos_left[abs(s[i])].push_back(i);
        else pos_right[s[i]].push_back(i);
    }

    vector<int> target(n);
    vector<bool> processed(n, false);
    int current_target = 0;

    for (int i = 0; i < n; i++) {
        if (processed[i]) continue;

        int size = abs(s[i]);
        int l_idx, r_idx;

        // Juftlikni topamiz
        l_idx = pos_left[size].front(); pos_left[size].pop_front();
        r_idx = pos_right[size].front(); pos_right[size].pop_front();

        // Qoidaga ko'ra chap poyabzal (-size) birinchi turishi kerak
        processed[l_idx] = processed[r_idx] = true;
        target[l_idx] = current_target++;
        target[r_idx] = current_target++;
    }

    // BIT yordamida inversiyalarni hisoblaymiz
    BIT bit(n);
    ll total_swaps = 0;
    for (int i = 0; i < n; i++) {
        // Element o'zidan o'ngda turgan, lekin aslida chapda bo'lishi kerak bo'lganlarni sanaydi
        total_swaps += i - bit.query(target[i]);
        bit.update(target[i] + 1, 1);
    }

    return total_swaps;
}

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