Contest Duration: - (local time) (100 minutes) Back to Home

## C - Poem Online Judge Editorial by en_translator

There are several ways to solve this problem. For example, can we solve it by inspecting one-by-one with for-loop? The following procedure is possible, for instance.

• Prepare a variable for the preliminary best submission best and its score best_score.
• Inspect the submissions in the increasing order of their indices from the $$!$$-st submission. When inspecting the $$i$$-th submission, first check if the submission is original.
• If the submission is original, check if the score $$T_i$$ is greater than best_score.
• If it is greater, let best be i and best_score be T_i.
• Otherwise, do nothing.
• If the submission isn’t original, do nothing.

The following is a naive implementation in Python with double for-loops.
However, it costs $$\mathrm{O}(N)$$ time to determine if Submission $$i$$ is original, for a total cost of $$\mathrm{O}(N^2)$$, which leads to TLE (Time Limit exceeded).

# TLE submission

N = int(input())
S, T = [], []
for i in range(N):
s, t = input().split()
S.append(s)
T.append(int(t))

best = -1
best_score = -1

for i in range(N):
original = True
for j in range(i):
if S[i] == S[j]:
original = False
if original == False:
continue
if best_score < T[i]:
best = i
best_score = T[i]

print(best + 1)


Instead, let’s manage the strings appeared so far with a set type or a associative array (dictionary) like a set in Python or a std::set in C++.
The set is a data structure which enables the following operation in an $$\mathrm{O}(1)$$ or $$\mathrm{O}(\log (\text{the number of elements}) )$$ time.

• Determine if a string is contained in the set
• Insert a string to the set

With such a data structure, the bottleneck of “determining if string has appeared before” can be done fast enough, so that you can get AC (Accepted).

# AC submission

N = int(input())
S, T = [], []
for i in range(N):
s, t = input().split()
S.append(s)
T.append(int(t))

best = -1
best_score = -1

appeared = set()
for i in range(N):
if S[i] in appeared:
continue