Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> merge(vector<vector<int> >&v,int k){
- vector<int>pointers(k,0);
- vector<int>ans;
- priority_queue<pair<int,int> >pq;
- do{
- pair<int,int> mini={INT_MAX,0};
- for(int i=0;i<k;i++){
- if(pointers[i]<v[i].size()){
- if(mini.first>v[i][pointers[i]]){
- mini={v[i][pointers[i]],i};
- }
- }
- }
- if(!pq.empty()){
- int num=pq.top().first;
- pq.pop();
- ans.push_back(num);
- // cout<<num<<" ";
- }
- if(mini.first!=INT_MAX){
- int index=mini.second;
- pointers[index]++;
- pq.push(mini);
- // cout<<mini.first<<" "<<index<<endl;
- }
- }while(!pq.empty());
- return ans;
- }
- int main() {
- int k;
- cin>>k;
- vector<vector<int> >v(k);
- for(int i=0;i<k;i++){
- vector<int>temp;
- int n;
- cin>>n;
- for(int j=0;j<n;j++){
- int c;
- cin>>c;
- temp.push_back(c);
- }
- v[i]=temp;
- }
- vector<int> ans=merge(v,k);
- for(int i=0;i<ans.size();i++){
- cout<<ans[i]<<" ";
- }
- // for(int i=0;i<k;i++){
- // for(int j=0;j<v[i].size();j++){
- // cout<<v[i][j]<<" ";
- // }
- // cout<<endl;
- // }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement