Submission #1089390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089390		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	0 ms	348 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

// Fenwick Tree (Binary Indexed Tree) for efficient range queries and updates
struct FenwickTree {
    int size;
    vector<int> tree;

    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    // Update the tree at position idx by adding delta
    void update(int idx, int delta = 1) {
        while (idx <= size) {
            tree[idx] += delta;
            idx += idx & (-idx);
        }
    }

    // Query the prefix sum up to and including idx
    int query(int idx) const {
        int res = 0;
        int i = idx;
        while (i > 0) {
            res += tree[i];
            i -= i & (-i);
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    string C;
    cin >> C;

    // Count frequencies of each color
    unordered_map<char, int> freq;
    for(char c : C){
        freq[c]++;
    }

    // Check feasibility
    int max_freq = 0;
    for(auto &[c, cnt] : freq){
        if(cnt > max_freq){
            max_freq = cnt;
        }
    }
    if(max_freq > (N +1)/2){
        cout << "-1";
        return 0;
    }

    // Priority queue to build the target sequence
    // Each element is a pair of (remaining_count, color)
    priority_queue<pair<int, char>> pq;
    for(auto &[c, cnt] : freq){
        pq.emplace(cnt, c);
    }

    string target = "";
    char prev = '#'; // Initialize with a dummy character
    while(!pq.empty()){
        auto [cnt, c] = pq.top(); pq.pop();
        if(c == prev){
            if(pq.empty()){
                // Cannot rearrange to meet the condition
                cout << "-1";
                return 0;
            }
            auto [cnt2, c2] = pq.top(); pq.pop();
            target += c2;
            prev = c2;
            if(--cnt2 >0){
                pq.emplace(cnt2, c2);
            }
            pq.emplace(cnt, c); // Put back the previous color
        }
        else{
            target += c;
            prev = c;
            if(--cnt >0){
                pq.emplace(cnt, c);
            }
        }
    }

    // Now, target contains a valid rearranged sequence
    // Next, compute the minimal number of adjacent swaps to convert C to target

    // For each character, store the list of indices where it appears in original sequence
    unordered_map<char, queue<int>> char_indices;
    for(int i=0;i<N;i++){
        char_indices[C[i]].push(i);
    }

    // Initialize Fenwick Tree
    FenwickTree ft(N);
    long long swaps =0;
    vector<int> pos_in_original(N);
    for(int i=0;i<N;i++) pos_in_original[i] = i;

    for(int i=0;i<N;i++){
        char current_char = target[i];
        if(char_indices[current_char].empty()){
            // This should not happen as we have a valid target
            cout << "-1";
            return 0;
        }
        int original_pos = char_indices[current_char].front();
        char_indices[current_char].pop();
        // Number of elements already moved that are before original_pos
        int moved_before = ft.query(original_pos +1);
        // The current position in the array after accounting for moved elements
        int current_swaps = original_pos - i - moved_before;
        if(current_swaps <0){
            // This should not happen
            cout << "-1";
            return 0;
        }
        swaps += current_swaps;
        // Mark this position as moved
        ft.update(original_pos +1);
    }

    cout << swaps;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25