main.cpp (1329B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 7 using namespace std; 8 9 // - documents 1 to n 10 // - n commands where we do the following for each instruction 11 // 1. scan - place document i on top of memory 12 // 2. print - iff memory not empty, print topmost and pop, else print i 13 // 3. quick print - prints document i 14 15 int main() { 16 17 int testCases, n; 18 string s; 19 cin >> testCases; 20 21 for(int x = 0; x < testCases; ++x) { 22 23 cin >> n; 24 cin >> s; 25 26 unordered_set<int> printed {}; 27 28 vector<int> stack {}; 29 30 for(int i = 0; i < n; ++i) { 31 if(s[i] == '1') { 32 stack.push_back(i); 33 } 34 else if(s[i] == '2') { 35 if(stack.size() > 0) { 36 printed.insert(stack[stack.size() - 1]); 37 stack.pop_back(); 38 } else { 39 printed.insert(i); 40 } 41 } 42 else if(s[i] == '3') { 43 printed.insert(i); 44 } 45 } 46 47 std::cout << n - printed.size() << std::endl; 48 49 for(int i = 0; i < n; ++i) { 50 if(!printed.contains(i)) { 51 std::cout << i + 1 << " "; 52 } 53 } 54 std::cout << std::endl; 55 } 56 }