c.cpp (1995B)
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 int main() { 13 int testCases, current, eles; 14 cin >> testCases; 15 16 for(int z = 0; z < testCases; ++z) { 17 // n books with height arr 18 // put books in any order I want 19 // visible from the right if strictly taller than all elements on othe right of it 20 21 // find max number of visible books at a given time 22 // sum left visible + right visible 23 24 // this has be be ~ linear time (possible sorting) 25 // can we just sort then alternate? 26 27 // 1 2 2 3 3 3 28 // 1 2 3 3 3 2 29 // sum = 5 30 // print any output that's valid 31 32 cin >> eles; 33 34 vector<int> ls {}; 35 for(int i = 0; i < eles; ++i) { 36 cin >> current; 37 ls.push_back(current); 38 } 39 40 41 sort(ls.begin(), ls.end()); 42 43 vector<int> fin (ls.size(), 0); 44 45 int left = 0; 46 int right = ls.size() - 1; 47 int visible = 0; 48 49 for(int i = 0; i < ls.size(); ++i) { 50 if(i % 2 == 0) { 51 fin[left] = ls[i]; 52 53 if(left != 0) { 54 if(fin[left] > fin[left-1]) { 55 visible += 1; 56 } 57 } else { 58 visible += 1; 59 } 60 61 left += 1; 62 } else { 63 fin[right] = ls[i]; 64 if(right != ls.size() - 1) { 65 if(fin[right] > fin[right+1]) { 66 visible += 1; 67 } 68 } else { 69 visible += 1; 70 } 71 right -= 1; 72 } 73 } 74 75 cout << visible << endl; 76 for(int i = 0; i < ls.size(); ++i) { 77 cout << fin[i] << " "; 78 } 79 cout << endl; 80 81 82 } 83 }