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 }