Submission #156252

---

Source Code Expand

#!/usr/bin/env python2.7

import sys
from collections import namedtuple, defaultdict
from bisect import bisect

from cStringIO import StringIO
import unittest
import cProfile

def main():
    N, = (int(x) for x in sys.stdin.readline().split())
    cn = list()
    for _ in xrange(N):
        c, = (int(x) for x in sys.stdin.readline().split())
        cn.append(c)
    print solve(cn)

def solve(cn):
    N = len(cn)
    
    best = [0]
    for i in xrange(N):
        c = cn[i]
        j = bisect(best, c)
        if j == len(best):
            best.append(c)
        else:
            best[j] = c

    return N - len(best) + 1
        
    
class Test(unittest.TestCase):

    @staticmethod
    def tryone(indata):
        sys.stdin = StringIO(indata)
        out = sys.stdout = StringIO()
        main()
        return out.getvalue()

    def test50(self):
        self.assertEqual(solve([1,3,5,2,4,6]), 2)
        self.assertEqual(solve([5,4,3,2,1]), 4)
        self.assertEqual(solve([1,2,3,4,5,6,7]), 0)

    def test80(self):
        self.assertEqual(solve(list(range(1, 1001))), 0)
        self.assertEqual(solve(list(range(1000, 0, -1))), 999)

    def test81(self):
        self.assertEqual(solve(list(range(1, 30000))), 0)
        self.assertEqual(solve(list(range(30000, 0, -1))), 29999)

    def test91(self):
        self.assertEqual(self.tryone("""\
6
1
3
5
2
4
6
"""), """2\n""")

if __name__ == '__main__':
    if len(sys.argv) > 1:
        print "_/" * 30 + str(sys.argv)
        if sys.argv[1] == '-p':
            sys.argv.pop(1)
            cProfile.run("unittest.main(exit=False, failfast=True)", sort='time')
        else:
            unittest.main()
    else:
        main()

Submission Info

Judge Result