IITKESO207PA3Q1 - Memory Game 1
Nitish has challenged Mahesh to a memory contest. The challenge is as follows. Nitish will ask Mahesh to remember 10-letter words and later answer queries on the words he has memorized. The commands as are follows:
1) learn: This command is used by Nitish to ask Mahesh to remember a word. Mahesh must add this word to the list of his remembered words.
2) reportsmallest: This command is used by Nitish to ask for the lexicographically smallest word from the words that Mahesh currently knows.
3) forgetsmallest: This command is used by Nitish to ask Mahesh to forget the lexicographically smallest word. Essentially, Mahesh must delete this word from his dictionary.
Mahesh has asked for your help in this task. You are required to design and implement a suitable data structure which supports the following time bounds (n is the number of words currently in the dictionary).
Input
The first line contains an integer q: the number of operations. q lines follow.
For each of the next q lines, there is one of three possibilites.
learn xyz - Mahesh must add the word "xyz" to his dictionary. Each word has 10-letters. Words contain only lowercase english letters from 'a' to 'z'.
reportsmallest - Mahesh must report the lexicographically smallest word in his dictionary
forgetsmallest - Mahesh must forget the lexicographically smallest word in his dictionary
Output
Print nothing for the learn operation.
For the reportsmallest opearation, print the answer (lexicographically smallest word in Mahesh's dictionary).
For the forgetsmallest operation, print the word that Mahesh must forget.
Constraints
1 <= q <= 5 * 10^5
Example
Input:
10
learn hawzslzptx
learn ifvubuhzjh
learn qyxhjloxym
reportsmallest
learn agcchgaiej
reportsmallest
forgetsmallest
reportsmallest
learn ebkajcggah
reportsmallest
Output:
hawzslzptx
agcchgaiej
agcchgaiej
hawzslzptx
ebkajcggah
hide comments
Programming Club, IITK:
2018-02-05 19:04:15
@ymahajan98: Yes |
|
ymahajan98:
2018-02-05 14:24:22
Am I allowed to use vectors for this question? |
Added by: | Programming Club, IITK |
Date: | 2018-02-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |