L-L
unknown
c_cpp
a year ago
1.9 kB
34
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