algorithms

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

problem.txt (2083B)


      1 B. Did Not Go to Print
      2 time limit per test2 seconds
      3 memory limit per test256 megabytes
      4 Recently, K1o0n bought himself a new expensive printer, which is distinguished by its memory, that is, it may not print immediately. Yesterday, while he was away from his new purchase, his friends used the printer.
      5 
      6 There are n
      7  documents numbered from 1
      8  to n
      9 . Initially, the printer memory is empty. The friends sequentially performed n
     10  commands on the printer, where the i
     11 -th command can be one of:
     12 
     13 '1'  — scanning. Document i
     14  is sent to the device memory and is placed on top of everything already there.
     15 '2'  — printing from memory. If the memory is not empty, the device prints the topmost document in memory and removes it from there. Otherwise, the device prints document i
     16 .
     17 '3'  — quick print. The device prints document i
     18 .
     19 Today, the friends came to K1o0n with a complaint — not all documents were printed. Help K1o0n find the indices of all documents that were not printed.
     20 
     21 Input
     22 The first line contains an integer t
     23  (1≤t≤104
     24 ) — the number of testcases.
     25 
     26 The first line of each testcase contains an integer n
     27  (1≤n≤2⋅105
     28 ) — the number of documents.
     29 
     30 The second line of each testcase contains a string s
     31  of length n
     32 , consisting of the characters '1', '2' and '3' — the friends' commands.
     33 
     34 It is guaranteed that the sum of n
     35  over all testcases does not exceed 2⋅105
     36 .
     37 
     38 Output
     39 For each testcase, output two lines.
     40 
     41 In the first line — the number k
     42  of documents that were not printed.
     43 
     44 In the second line — their numbers in increasing order, separated by spaces. If k=0
     45 , the second line is empty.
     46 
     47 ---
     48 
     49 - documents 1 to n
     50 - n commands where we do the following for each instruction
     51     1. scan - place document i on top of memory
     52     2. print - iff memory not empty, print topmost and pop, else print i
     53     3. quick print - prints document i
     54 
     55 ---
     56 
     57 examples
     58 
     59 
     60 
     61 2
     62 12
     63 
     64 
     65 n = 2
     66 s = 12 (n commands)
     67 
     68 place 1 on top
     69 print 1
     70 
     71 not printed 2
     72 
     73 ---
     74 
     75 2
     76 13
     77 
     78 n = 2
     79 s = 13
     80 
     81 push 1 onto stack
     82 print 2
     83 
     84 return 1 and 1
     85 
     86 ---
     87 
     88 2
     89 23
     90 
     91 
     92 
     93 ---
     94 
     95 6
     96 112332
     97 3
     98 112
     99 6
    100 211213