Hmmm, I think this problem is easily solved in O(n).dumb dan wrote:This problem can be solved in O(n log n). Or faster if input is nice, but we have no reason to believe input is nice.

You need a queue and an array sized twice the biggest number in input.

This is the pseudo code of this easy solution

Code: Select all

```
loop
if EOF
exit loop
endif
read number
if count of number is zero
enqueue number
endif
increase count of number
end loop
while queue not empty
dequeue number
print number, count of number
end while
```

As you can see it's close enough to those of Scott and Ivor. You can also notice that Scott and Ivor solved this problem in 2002 probably before the upgrade of the OJ.

Before the upgrade the resolution of runtime measurements was 10 or 20 milliseconds and so probably they got 0:00.000 because of this.

I hope this cleared any doubts on the speed of some submissions.

Ciao!!!

Claudio