IOI '12 - Sirmione/Montichiari, Italy

Crayfish Scrivener

Some people say that Leonardo was a great admirer of Johannes Gutenberg, the German blacksmith who invented movable-type printing, and that he paid homage by designing a machine called the crayfish scrivener — il gambero scrivano — a very simple typing device. It is somehow similar to a simple modern typewriter and accepts only two commands: one to type the next character and one to undo the most recent commands. The notable feature of the crayfish scrivener is that the undo command is extremely powerful: an undo is also considered to be a command itself, and can be undone.

Statement

Your task is to realize a software version of the crayfish scrivener: it starts with an empty text and accepts a sequence of commands entered by the user, and queries for specific positions of the current version of the text, as follows.

• TypeLetter L — append to the end of the text a single lowercase letter L chosen from a, …, z.
• UndoCommands U — undo the the last U commands, for a positive integer U.
• GetLetter P — output the letter at position P in the current text, for a non-negative index P. The first letter in the text has index 0. (This query is not a command and thus is ignored by the undo command.)

These operations can be called zero or more times in any order. It is guaranteed that U will not exceed the number of previously received commands, and that P will be less than the current text length (the number of letters in the current text).

As for UndoCommands U, it undoes the previous U commands in reverse order: if the command to be undone is TypeLetter L, then it removes L from the end of the current text; if the command to be undone is UndoCommands X for some value X, it re-does the previous X commands in their original order.

Input Format

Your program must read the input in the following format:

• line 1: the total number of commands and queries in the input;
• on each following line:
• • T followed by a space and a lowercase letter for a TypeLetter command;
  • U followed by a space and an integer for UndoCommands;
  • P followed by a space and an integer for GetLetter.

Example

We show a possible sequence of calls, together with the state of the text after each call.

14

Subtask 1 [5% of points]

The total number of commands and queries is between 1 and 100 (inclusive) and there will be no calls to UndoCommands.

Subtask 2 [7% of points]

The total number of commands and queries is between 1 and 100 (inclusive) and no UndoCommands will be undone.

Subtask 3 [22% of points]

The total number of commands and queries is between 1 and 5 000 (inclusive).

Subtask 4 [26% of points]

The total number of commands and queries is between 1 and 1 000 000 (inclusive). All calls to GetLetter will occur after all calls to TypeLetter and UndoCommands.

Subtask 5 [40% of points]

The total number of commands and queries is between 1 and 1 000 000 (inclusive).

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Aug 12, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Why am I getting runtime error on subtasks 4,5 can someone help me

Signal 6 (SIGABRT) in C++ tends to be caused by your program aborting due to an uncaught exception. In the STL, this commonly happens because bad_alloc is thrown but not caught, meaning you've run out of memory.

Indeed, this is what has happened in your submission.

I checked my code with test cases from the olympiad itself and it prints the right answer, but still the grader gives me wrong answer for each test case.

No, your program is just wrong. Hint: try compiling with [code]g++ -g -fsanitize=address[/code].

g++ -g -fsanitize=address

Wrong test data. I downloaded test data and my program outputs exactly what it should output, but here it gives WA....

Edit:You need to output letters on new lines. 

O(1) for Type and Undo
O(log N) for GetLetter

Edit: Java is just slow :(

You barely miss it! You might've passed if you used custom, faster input functions.

[code][quote]Test case #4a: AC [2.092s, 288K]
Test case #4b: AC [2.172s, 288K]
Test case #4f: AC [2.182s, 288K]
Test case #4i: AC [2.216s, 288K]
Test case #5a: AC [2.002s, 288K]
Test case #5b: AC [2.092s, 288K]
Test case #5i: AC [2.012s, 288K][/quote][/code]

            

            

            
            

            
Test case #4a: AC [2.092s, 288K] 
Test case #4b: AC [2.172s, 288K] 
Test case #4f: AC [2.182s, 288K] 
Test case #4i: AC [2.216s, 288K] 
Test case #5a: AC [2.002s, 288K] 
Test case #5b: AC [2.092s, 288K] 
Test case #5i: AC [2.012s, 288K]