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, -- http://mail.python.org/mailman/listinfo/python-list
