L-L

 avatar
unknown
c_cpp
a year ago
1.9 kB
29
Indexable
#include <bits/stdc++.h>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    int n, k;
    cin >> n;
    cin >> k;

    priority_queue <vector <int>> pq;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;

        vector <int> vec;
        vec.push_back(val);
        vec.push_back(i);
        vec.push_back(0);
        vec.push_back(i);
        pq.push(vec);
    }

    int toggle = 1;
    priority_queue <vector <int>, vector<vector <int>>, greater<vector <int>>> final_pq;
    while (!pq.empty()) {
        int max_val = pq.top()[0];
        int max_pos = pq.top()[1];

        vector <int> pos_vec;
        priority_queue <vector <int>> new_pq;
        while (!pq.empty()) {
            int cur_pos = pq.top()[1];
            vector <int> vec(pq.top());
            pq.pop();
            if (abs(max_pos - cur_pos) <= k) {
                // cout << vec[0] << " - " << toggle << "\n";
                pos_vec.push_back(cur_pos);
                vec[2] = toggle;
                swap(vec[0], vec[3]);
                final_pq.push(vec);
            } else {
                // cout << "printing pos vector" << cur_pos << "\n";
                int temp = cur_pos;
                for (auto val : pos_vec) {
                    if (val < cur_pos) {
                        temp--;
                    }
                }
                // cout << "\n";
                vec[1] = temp;
                // cout << "Changed - " << temp << "\n";
                new_pq.push(vec);
            }
        }
        pq = new_pq;
        if (toggle == 1) toggle = 2;
        else toggle = 1;
    }

    while (!final_pq.empty()) {
        vector <int> vec(final_pq.top());
        cout << vec[2];
        final_pq.pop();
    }
    return 0;
}
Editor is loading...
Leave a Comment