L-L
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