Submit | All submissions | Best solutions | Back to list |
TICKETS - Ticket Verlosung |
Byteland organisiert die Fußball WM. Ein Radiosender hat einige der Eintrittskarten erworben und bietet eine Verlosung an. Genauer gesagt handelt es sich hierbei um ein Telefonspiel, bei dem jeder Teilnehmer eine Zahl zwischen 1 und 109 wählen kann, and am Ende jeden Tages bekommt derjenige eine Eintrittskarte, der die k.-kleinste Zahl gewählt hat. Um zu verhindern, dass es mehr als einen Gewinner gibt, darf jede Zahl nur einmal gewählt werden. Falls also ein Teilnehmer eine Zahl wählt, die schon vergeben ist, muss er einfach noch einmal wählen.
Martin, ein fanatischer Fußballfan ohne Eintrittskarten, hat Robert H., einen Angestellten des Radiosenders, bestochen und ihm Geschenke versprochen für den Fall, dass er ihm eine derzeitige Gewinnzahl nennt: "Einen Korb mit Spezialitäten aus dem Schwarzwald, der einige richtig gute Würstchen enthält, Schinken, und - halten Sie sich fest - eine wunderschöne Kuckucksuhr! Und dazu noch einen Bierkrug! Wie können Sie da widerstehen?"
Natürlich konnte Robert diesem verlockenden Angebot nicht widerstehen und braucht nun ein Programm, das ihm zu beliebigen Zeiten während dem Spiel die k.-kleinste Zahl berechnet.
Eingabe
Die erste Zeile in der Eingabe enthält eine Zahl c (1 ≤ c ≤ 106), die angibt, wieviele Telefonanrufe der Sender bekommt. Die folgende Zeile der Eingabe enthält die Zahl k (1 ≤ k ≤ min(c, 100000) ). Die folgenden c Zeilen geben die gewählten Zahlen der Teilnehmer des Gewinnspiels an in der zeitlichen Reihenfolge ihrer Anrufe bei dem Radiosender. Alle diese Zahlen liegen zwischen 0 und 109, wobei eine Zahl 0 bedeutet, dass Martin Robert angerufen hat und wissen will, was die derzeit k.-kleinste Zahl ist. Die Zahl 0 wird hierbei nicht in die Liste möglicher Gewinnzahlen aufgenommen. Für alle Zahlen > 0 gilt, dass sie nur einmal in der Eingabe vorkommen.
Ausgabe
Geben Sie für jede Zahl 0 in der Eingabe, die einem Anruf von Martin entspricht, eine Zeile aus mit der k.-kleinsten Zahl zu diesem Zeitpunkt. Falls bis dahin noch keine k Zahlen gewählt wurden, geben Sie -1 aus.
Beispiel
Eingabe: 7 2 4711 0 1337 0 210706 3 0 Ausgabe: -1 4711 1337
Achtung! Die Anzahl der Abfragen nach der k.-kleinsten Zahl kann sehr groß sein (z. B. jeder zweite Anruf). Eine effiziente Datenstruktur wird benötigt.
Added by: | Adrian Kuegel |
Date: | 2008-10-27 |
Time limit: | 10s-32s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |