algorithms

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

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 }