List of integers & L.I.S. (SPOILER)
Bryan Olson
fakeaddress at nowhere.org
Fri Sep 9 04:50:39 EDT 2005
n00m wrote:
> Bravo, Bryan!
> It's incredibly fast!
Not compared to a good implementation for a compiled, low-level
language.
> But your code got WA (wrong answer).
> See my latest submission: http://spoj.sphere.pl/status/SUPPER/
> Maybe you slipped a kind of typo in it? Silly boundary cases?
Hmmm ... wrong answer ... what could ... ah! Here's a problem: I
bomb on the empty sequence. Correction below.
I'm not a perfect programmer, but I like to think I'm a good
programmer. Good programmers own their bugs.
If there's another problem, I need more to go on. From what you
write, I cannot tell where it fails, nor even what submission is
yours and your latest.
--
--Bryan
#!/user/bin/env python
"""
Python solution to:
http://spoj.sphere.pl/problems/SUPPER/
By Bryan Olson
"""
from sys import stdin
def one_way(seq):
n = len(seq)
dominators = [n + 1] * (n * 1)
score = [None] * n
end = 0
for (i, x) in enumerate(seq):
low, high = 0, end
while high - low > 10:
mid = (low + high) >> 1
if dominators[mid] < x:
low = mid + 1
else:
high = mid + 1
while dominators[low] < x:
low += 1
dominators[low] = x
score[i] = low
end = max(end, low + 1)
return score
def supernumbers(seq):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_way(opposite))
score = map(sum, zip(forscore, backscore))
winner = max(score + [0])
return sorted([seq[i] for i in range(len(seq)) if score[i] == winner])
_ = stdin.readline()
sequence = [int(ch) for ch in stdin.readline().split()]
supers = supernumbers(sequence)
print len(supers)
for i in supers:
print i,
More information about the Python-list
mailing list