algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

d.cpp (1513B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 // ufo has array a of length n
     13 // ufo makes b of length n s.t.
     14     // a_i is a mode of [b_1,b_2,...,b_i] for all 1 <= i <= n
     15 
     16 int main() {
     17     int testCases, ln, current;
     18 
     19     cin >> testCases;
     20 
     21 
     22     for(int z = 0; z < testCases; ++z) {
     23 
     24         cin >> ln;
     25         vector<int> ls {};
     26 
     27         for(int i = 0; i < ln; ++i) {
     28             cin >> current;
     29             ls.push_back(current);   
     30         }
     31 
     32         unordered_set<int> bContains {};
     33         unordered_set<int> aContains {};
     34         vector<int> b (ls.size());
     35 
     36         vector<int> nextMissing {};
     37 
     38         for(int i = 0; i < ls.size(); ++i) {
     39             aContains.insert(ls[i]);
     40         }
     41 
     42         for(int i = 0; i < ls.size(); ++i) {
     43             if(aContains.contains(i+1)) {
     44                 continue;
     45             }
     46             nextMissing.push_back(i+1);
     47         }
     48 
     49         int nx = 0;
     50 
     51         // iff the ls[i] is not in b, then add it. otherwise, add a number <= n that isn't in the array a.
     52         for(int i = 0; i < ls.size(); ++i) {
     53             if(bContains.contains(ls[i])) {
     54                 b[i] = nextMissing[nx];
     55                 nx += 1;
     56             } else {
     57                 b[i] = ls[i];
     58                 bContains.insert(ls[i]);
     59             }
     60         }
     61         for(int i = 0; i < ls.size(); ++i) {
     62             cout << b[i] << " ";
     63         }
     64         cout << endl;
     65     }
     66 }