<PREV Problem:
NEXT>
Solved by 174 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Radio

Time limit = 3 second(s)

New company "Audio square" have conqured the major part of online audio streaming market. It provides personal radio for each human. But now "Audio Square" CEOs decided to publish new feature — Public Radio.

Public Radio has one audio stream where tracks successively change each other.

Its algorithm is simple but still promises considerable social satisfaction. Visitors of the public radio web site vote for tracks they want to listen or don't want to listen thus changing track_score of the tracks. One IP address is allowed to vote only once in 10 minutes (two votes should be separated by 600 seconds or more).

Next track is the track with maximum score. If two tracks have equal score track with lower id is preferred one. The moment track starts to play its score resets to -1.

You are the chief developer of "Audio square". You have professional stuff to do the job, but this time you prefer to do it by yourself (to revive your professional programmer skills).

Your task is to make algorithm efficient so that radio does not use much processor time and memory.

The program interacts with server via standard input/output and uses the following protocol.

Input

Each input line is command. There are three command types:

VOTE    

The command VOTE change track_score of the given track with id track_id. Its arguments are

Response to VOTE is new track_score (even if it have not changeed)

The command GET is used to get next track to play. The response is pair track_id and track_score separated by space. Just after this command track_score of the track should be reset to -1.

The command EXIT is in the last line. The response is line ``OK''.

Number of commands is less than 100002.

The initial value of track_score is equal to 0 for all tracks.

Commands in input are odered by execution time.

Output

Output should contain the same number of lines as input. Each line contains response to corresponding command from input.

Input#1
GET
VOTE 1.1.1.1 1 -1 1
VOTE 1.1.1.1 2 1 2
VOTE 1.1.1.1 1 2 4
VOTE 1.1.1.1 1 4 20045
GET
GET
GET
VOTE 194.85.81.128 3 -1 20049
EXIT
Output#1
1 0
-2
0
-2
2
1 2
2 0
3 0
-2
OK

Input#2
GET
GET
GET
VOTE 192.168.0.1 2 2 11111111
EXIT
Output#2
1 0
2 0
3 0
1
OK

Author:
Artem Voroztsov, Personal Programming MIPT Contest, 7 October 2007.
4 December 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.198.246.116