Ankit_132

Mex Array

Jun 28th, 2023
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll     long long
  6. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  7. #define pb     push_back
  8.  
  9. int main()
  10. {
  11.     _test
  12.     {
  13.         int n;
  14.         cin>>n;
  15.  
  16.         vector<int> a(n);
  17.         for(auto &e: a)     cin>>e;
  18.  
  19.         vector<int> ans;
  20.         multiset<int> mst;
  21.  
  22.         for(auto e: a)
  23.             mst.insert(e);
  24.  
  25.         while(mst.size() && *mst.begin()==0)
  26.         {
  27.             int mex = 0;
  28.             while(mst.find(mex) != mst.end())
  29.             {
  30.                 mst.erase(mst.find(mex));
  31.                 mex++;
  32.             }
  33.  
  34.             ans.pb(mex);
  35.         }
  36.  
  37.         for(int i=0; i<mst.size(); i++)
  38.             ans.pb(0);
  39.  
  40.         cout<<ans.size()<<"\n";
  41.         for(auto e: ans)
  42.             cout<<e<<" ";
  43.         cout<<"\n";
  44.     }
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment