Submission #1310164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310164		ayuxhkumxr22	Exercise Deadlines (CCO20_day1problem2)	C++20	25 / 25	55 ms	14476 KiB

Main

/*
Author : ayuxh
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long

// Fenwick Tree (BIT) for Inversion Counting
struct FenwickTree {
    int size;
    vector<int> tree;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void add(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx) tree[idx] += delta;
    }
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) sum += tree[idx];
        return sum;
    }
};

void Solve() {
    int n;
    if (!(cin >> n)) return;

    // deadlines[d] stores list of task IDs that have deadline d
    vector<vector<int>> tasks_by_deadline(n + 1);
    for (int i = 1; i <= n; ++i) {
        int d;
        cin >> d;
        tasks_by_deadline[d].push_back(i);
    }

    priority_queue<int> pq; // Max-heap: Stores task IDs available to be placed
    vector<int> result_permutation(n + 1);

    // Fill positions from N down to 1
    for (int pos = n; pos >= 1; --pos) {
        // Add tasks that become available at this deadline
        // (i.e., tasks with deadline exactly 'pos' can certainly be placed at 'pos' or earlier)
        // Wait, logic check: A task with deadline D can be placed at any pos <= D.
        // So at pos=N, we can use tasks with deadline N.
        // At pos=N-1, we can use tasks with deadline N-1 AND unused tasks from deadline N.
        for (int task_id : tasks_by_deadline[pos]) {
            pq.push(task_id);
        }

        if (pq.empty()) {
            cout << "-1\n";
            return;
        }

        // Greedy choice: Pick the largest available task ID
        int task_to_place = pq.top();
        pq.pop();

        // We place this task at the current position 'pos'
        result_permutation[pos] = task_to_place;
    }

    // Now calculate minimum swaps to transform 1..N to result_permutation.
    // This is equivalent to counting inversions, or more directly:
    // The cost is the sum of distances of moves.
    // Actually, since we know the target positions, we can use a standard inversion count.
    // The problem asks for swaps to transform (1..N) -> result_permutation.
    // Let's re-verify sample 1:
    // N=4, D=[4, 4, 3, 2]. Tasks: 1(d=4), 2(d=4), 3(d=3), 4(d=2).
    // Pos 4: Pool has {1, 2}. Pick 2. Perm[4] = 2.
    // Pos 3: Pool has {1} + {3}. Pick 3. Perm[3] = 3.
    // Pos 2: Pool has {1} + {4}. Pick 4. Perm[2] = 4.
    // Pos 1: Pool has {1}. Pick 1. Perm[1] = 1.
    // Result Perm: [1, 4, 3, 2].
    // Swaps 1,2,3,4 -> 1,4,3,2.
    // Inversions in [1, 4, 3, 2]:
    // (4, 3), (4, 2), (3, 2). Total 3. Correct.
    
    // Inversion Count using BIT
    // Iterate through the permutation, for each element x, how many elements > x appeared before it?
    // OR: for each element x, how many elements < x appear AFTER it?
    // Standard approach:
    FenwickTree ft(n);
    int inversions = 0;
    // Note: The result_permutation is 1-indexed from the logic above.
    for (int i = 1; i <= n; ++i) {
        int val = result_permutation[i];
        // Count elements greater than 'val' already processed (appearing to the left)
        // Actually standard way: Count elements > val already seen.
        // Query(n) - Query(val) gives count of numbers > val currently in tree.
        inversions += (i - 1) - ft.query(val);
        ft.add(val, 1);
    }
    
    cout << inversions << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Solve();
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8