TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

70.4% (19/27)

Submission's AC Ratio

11.3% (44/389)

Tags

Description

從前,襄國組織軍隊進攻安岱爾高原地區,史稱安襄戰爭。

這故事得從一個安岱爾志願軍的間諜,斯克里夫尼說起。斯克里夫尼是一個天才型的間諜,往來於各國之間,無往不利。由於常常蒐集情報,斯克里夫尼需要一個好方法整理他獲得的情報。

為了保持機密,斯克里夫尼將所有的情報分為26類,並編號為a, b, …, z。這26類的情報被放在不同的軍事基地裡面,因此為了方便檢索,在每一次的機密行動中,斯克里夫尼以一張紙條,按照獲得情報的順序把每一個「有效情報」的分類寫下來,成為一個字串,例如qegpnslkywotqhp。每當獲得一個新情報,就可以直接把新情報的分類寫在字串的最後方,十分方便。

然而,斯克里夫尼最近遇到了麻煩。要知道,在各國的諜戰當中,釋放假消息必然是一個常見的戰略。因此,斯克里夫尼常常需要「復原」最近對紙條所做的改變,例如他可能發現最近蒐集的12個情報都是假的,因此要把那些情報從紙條上移除(或者說那些情報成為「無效情報」);或者他發現「最近蒐集的12個情報都是假的」這個情報居然也是假的,那就要把那些情報再寫回去(也就是那些情報又成了「有效情報」)。大量的修改令斯克里夫尼十分困擾,因為如果紙條塗塗改改,就難以辨別真偽;然而,如果重新寫一張,要銷毀原本的紙條會十分麻煩,若處理不當甚至有機密外流的風險。

因此,斯克里夫尼找上了你。他希望你能幫他製作一個像是打字機的機器(這樣看起來比較不顯眼,萬一外流也比較不會被懷疑),提供下列幾個功能,以取代他原本的紙條:
1. Init:斯克里夫尼把機器開機,相當於提供一個空的紙條。
2. TypeLetter,並附帶一個字母Q,斯克里夫尼獲得了一個新的有效情報,分類為Q,相當於在紙條上的最後面再加一個Q。
3. UndoCommands,並附帶一個正整數K,斯克里夫尼獲得「前面K個獲得的情報都是假的」的情報,相當於復原紙條前N次做的修改。
注意:「前面K個獲得的情報都是假的」也算是一個情報,所以這個情報也必須可以被復原。
4. GetLetter,並附帶一個正整數P,斯克里夫尼想要知道從開頭數來第P個有效情報是哪一個分類(注意有效情報是從0開始編號),需要機器顯示一個字母。

因為斯克里夫尼很聰明,所以他操作機器絕對不會有失誤:在每一次的機密行動中,他會先將機器開機(使用Init),然後才會使用其它三個功能。當然,在使用UndoCommands的時候,K絕對不會超過目前獲得情報的數量;使用GetLetter的時候,第P個有效情報必然存在。

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#include "lib1271.h"之後實作下列四個函數。如果你的函數名稱不對或者長得不像下面那些行,你將會獲得一個CE。
void Init();
void TypeLetter(char);
void UndoCommands(int);
char GetLetter(int);
請依照題目敘述實作這四個函數。

在一次執行當中,斯克里夫尼可能會出很多次機密任務,所以請確保Init函數中有進行初始化與記憶體回收。

以下敘述以N代表呼叫TypeLetterUndoCommandsGetLetter次數的總和。
對於5%的測資,N ≤ 100;保證不會呼叫UndoCommands
對於7%的測資,N ≤ 100;保證UndoCommands的情報絕對是正確的(也就是不會被復原)。
對於22%的測資,N ≤ 5,000。
對於26%的測資,N ≤ 1,000,000;保證在一次的機密任務中,一但呼叫了GetLetter,就不會再呼叫TypeLetterUndoCommands
對於所有的測資,N ≤ 1,000,000。

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Hints

這裡有一個測試用的標頭檔,可以用來測試。

Problem Source

IOI 2012 Day 1
Judge / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 5
2 1 7
3 2 22
4 3 26
5 4 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 2
2 2000 262144 262144 3
3 7000 262144 262144 4
4 7000 262144 262144 5