Submission #1481401
Source Code Expand
#!/usr/bin/python import functools class SAComp: def __init__(self,h,g): self.h=h self.g=g def cmp(self,a,b): if a==b: return 0 if self.g[a]!=self.g[b]: return self.g[a]-self.g[b] return self.g[a+self.h]-self.g[b+self.h] def buildSA(t): n=len(t) g=list(map(ord,t)) b=[0]*n suff=list(range(n)) comp=SAComp(0,g) suff.sort(key=functools.cmp_to_key(comp.cmp)) h=1 while b[n-1]!=n-1: comp=SAComp(h,g) suff.sort(key=functools.cmp_to_key(comp.cmp)) for i in range(n-1): b[i+1]=b[i]+(comp.cmp(suff[i],suff[i+1])<0) for i in range(n): g[suff[i]]=b[i] h<<=1 return suff def buildLCP(t,suff): n=len(t) rank=[0]*n lcp=[0]*n for i in range(n): rank[suff[i]]=i h=0 for i in range(n-1): j=suff[rank[i]-1] if h>0: h-=1 while j+h<n and i+h<n and t[j+h]==t[i+h]: h+=1 lcp[rank[i]-1]=h return lcp def solve(s): s+='$' suff=buildSA(s) lcp=buildLCP(s,suff) return len(s)-1-max(lcp) import sys;print(solve(sys.stdin.readline().strip()))
Submission Info
Submission Time | |
---|---|
Task | G - Exam |
User | leafmoon |
Language | Python (2.7.6) |
Score | 60 |
Code Size | 1029 Byte |
Status | TLE |
Exec Time | 2105 ms |
Memory | 24300 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 30 / 30 | 0 / 140 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_small_000.txt, 00_small_001.txt, 00_small_002.txt, 00_small_003.txt, 00_small_004.txt, 00_small_005.txt, 00_small_006.txt, 00_small_007.txt, 00_small_008.txt, 00_small_009.txt, 00_small_010.txt, 00_small_011.txt, 00_small_012.txt, 00_small_013.txt, 00_small_014.txt, 00_small_015.txt, 00_small_016.txt, 00_small_017.txt, 00_small_018.txt, 00_small_019.txt, 00_small_020.txt, 00_small_021.txt, 00_small_022.txt, 00_small_023.txt, 00_small_024.txt, 00_small_025.txt, 00_small_078.txt, 00_small_079.txt, 00_small_080.txt, 00_small_081.txt, 00_small_082.txt, 00_small_083.txt, 00_small_084.txt, 00_small_085.txt, 00_small_086.txt, 00_small_087.txt, 00_small_108.txt, 00_small_109.txt, 00_small_110.txt, 00_small_111.txt, 00_small_112.txt, 00_small_113.txt, 00_small_114.txt, 00_small_115.txt, 00_small_116.txt, 00_small_117.txt, 00_teuchi_00.txt |
Subtask2 | 10_medium_026.txt, 10_medium_027.txt, 10_medium_028.txt, 10_medium_029.txt, 10_medium_030.txt, 10_medium_031.txt, 10_medium_032.txt, 10_medium_033.txt, 10_medium_034.txt, 10_medium_035.txt, 10_medium_036.txt, 10_medium_037.txt, 10_medium_038.txt, 10_medium_039.txt, 10_medium_040.txt, 10_medium_041.txt, 10_medium_042.txt, 10_medium_043.txt, 10_medium_044.txt, 10_medium_045.txt, 10_medium_046.txt, 10_medium_047.txt, 10_medium_048.txt, 10_medium_049.txt, 10_medium_050.txt, 10_medium_051.txt, 10_medium_088.txt, 10_medium_089.txt, 10_medium_090.txt, 10_medium_091.txt, 10_medium_092.txt, 10_medium_093.txt, 10_medium_094.txt, 10_medium_095.txt, 10_medium_096.txt, 10_medium_097.txt, 10_medium_118.txt, 10_medium_119.txt, 10_medium_120.txt, 10_medium_121.txt, 10_medium_122.txt, 10_medium_123.txt, 10_medium_124.txt, 10_medium_125.txt, 10_medium_126.txt, 10_medium_127.txt |
All | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_small_000.txt, 00_small_001.txt, 00_small_002.txt, 00_small_003.txt, 00_small_004.txt, 00_small_005.txt, 00_small_006.txt, 00_small_007.txt, 00_small_008.txt, 00_small_009.txt, 00_small_010.txt, 00_small_011.txt, 00_small_012.txt, 00_small_013.txt, 00_small_014.txt, 00_small_015.txt, 00_small_016.txt, 00_small_017.txt, 00_small_018.txt, 00_small_019.txt, 00_small_020.txt, 00_small_021.txt, 00_small_022.txt, 00_small_023.txt, 00_small_024.txt, 00_small_025.txt, 00_small_078.txt, 00_small_079.txt, 00_small_080.txt, 00_small_081.txt, 00_small_082.txt, 00_small_083.txt, 00_small_084.txt, 00_small_085.txt, 00_small_086.txt, 00_small_087.txt, 00_small_108.txt, 00_small_109.txt, 00_small_110.txt, 00_small_111.txt, 00_small_112.txt, 00_small_113.txt, 00_small_114.txt, 00_small_115.txt, 00_small_116.txt, 00_small_117.txt, 00_teuchi_00.txt, 10_medium_026.txt, 10_medium_027.txt, 10_medium_028.txt, 10_medium_029.txt, 10_medium_030.txt, 10_medium_031.txt, 10_medium_032.txt, 10_medium_033.txt, 10_medium_034.txt, 10_medium_035.txt, 10_medium_036.txt, 10_medium_037.txt, 10_medium_038.txt, 10_medium_039.txt, 10_medium_040.txt, 10_medium_041.txt, 10_medium_042.txt, 10_medium_043.txt, 10_medium_044.txt, 10_medium_045.txt, 10_medium_046.txt, 10_medium_047.txt, 10_medium_048.txt, 10_medium_049.txt, 10_medium_050.txt, 10_medium_051.txt, 10_medium_088.txt, 10_medium_089.txt, 10_medium_090.txt, 10_medium_091.txt, 10_medium_092.txt, 10_medium_093.txt, 10_medium_094.txt, 10_medium_095.txt, 10_medium_096.txt, 10_medium_097.txt, 10_medium_118.txt, 10_medium_119.txt, 10_medium_120.txt, 10_medium_121.txt, 10_medium_122.txt, 10_medium_123.txt, 10_medium_124.txt, 10_medium_125.txt, 10_medium_126.txt, 10_medium_127.txt, 20_large_052.txt, 20_large_053.txt, 20_large_054.txt, 20_large_055.txt, 20_large_056.txt, 20_large_057.txt, 20_large_058.txt, 20_large_059.txt, 20_large_060.txt, 20_large_061.txt, 20_large_062.txt, 20_large_063.txt, 20_large_064.txt, 20_large_065.txt, 20_large_066.txt, 20_large_067.txt, 20_large_068.txt, 20_large_069.txt, 20_large_070.txt, 20_large_071.txt, 20_large_072.txt, 20_large_073.txt, 20_large_074.txt, 20_large_075.txt, 20_large_076.txt, 20_large_077.txt, 20_large_098.txt, 20_large_099.txt, 20_large_100.txt, 20_large_101.txt, 20_large_102.txt, 20_large_103.txt, 20_large_104.txt, 20_large_105.txt, 20_large_106.txt, 20_large_107.txt, 20_large_128.txt, 20_large_129.txt, 20_large_130.txt, 20_large_131.txt, 20_large_132.txt, 20_large_133.txt, 20_large_134.txt, 20_large_135.txt, 20_large_136.txt, 20_large_137.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00.txt | AC | 13 ms | 2820 KB |
00_sample_01.txt | AC | 10 ms | 2696 KB |
00_sample_02.txt | AC | 10 ms | 2696 KB |
00_sample_03.txt | AC | 11 ms | 2696 KB |
00_small_000.txt | AC | 11 ms | 2696 KB |
00_small_001.txt | AC | 11 ms | 2696 KB |
00_small_002.txt | AC | 11 ms | 2696 KB |
00_small_003.txt | AC | 11 ms | 2696 KB |
00_small_004.txt | AC | 11 ms | 2696 KB |
00_small_005.txt | AC | 10 ms | 2696 KB |
00_small_006.txt | AC | 11 ms | 2696 KB |
00_small_007.txt | AC | 10 ms | 2696 KB |
00_small_008.txt | AC | 11 ms | 2696 KB |
00_small_009.txt | AC | 11 ms | 2696 KB |
00_small_010.txt | AC | 10 ms | 2696 KB |
00_small_011.txt | AC | 10 ms | 2696 KB |
00_small_012.txt | AC | 10 ms | 2696 KB |
00_small_013.txt | AC | 11 ms | 2696 KB |
00_small_014.txt | AC | 11 ms | 2696 KB |
00_small_015.txt | AC | 11 ms | 2696 KB |
00_small_016.txt | AC | 11 ms | 2696 KB |
00_small_017.txt | AC | 11 ms | 2696 KB |
00_small_018.txt | AC | 11 ms | 2696 KB |
00_small_019.txt | AC | 11 ms | 2696 KB |
00_small_020.txt | AC | 10 ms | 2696 KB |
00_small_021.txt | AC | 11 ms | 2696 KB |
00_small_022.txt | AC | 11 ms | 2696 KB |
00_small_023.txt | AC | 10 ms | 2696 KB |
00_small_024.txt | AC | 11 ms | 2696 KB |
00_small_025.txt | AC | 11 ms | 2696 KB |
00_small_078.txt | AC | 11 ms | 2696 KB |
00_small_079.txt | AC | 11 ms | 2696 KB |
00_small_080.txt | AC | 11 ms | 2696 KB |
00_small_081.txt | AC | 11 ms | 2696 KB |
00_small_082.txt | AC | 11 ms | 2696 KB |
00_small_083.txt | AC | 11 ms | 2696 KB |
00_small_084.txt | AC | 11 ms | 2696 KB |
00_small_085.txt | AC | 11 ms | 2696 KB |
00_small_086.txt | AC | 12 ms | 2752 KB |
00_small_087.txt | AC | 11 ms | 2696 KB |
00_small_108.txt | AC | 12 ms | 2696 KB |
00_small_109.txt | AC | 12 ms | 2696 KB |
00_small_110.txt | AC | 11 ms | 2696 KB |
00_small_111.txt | AC | 11 ms | 2696 KB |
00_small_112.txt | AC | 11 ms | 2696 KB |
00_small_113.txt | AC | 11 ms | 2696 KB |
00_small_114.txt | AC | 11 ms | 2696 KB |
00_small_115.txt | AC | 11 ms | 2696 KB |
00_small_116.txt | AC | 11 ms | 2696 KB |
00_small_117.txt | AC | 11 ms | 2752 KB |
00_teuchi_00.txt | AC | 10 ms | 2752 KB |
10_medium_026.txt | AC | 25 ms | 2816 KB |
10_medium_027.txt | AC | 29 ms | 2816 KB |
10_medium_028.txt | AC | 27 ms | 2816 KB |
10_medium_029.txt | AC | 26 ms | 2816 KB |
10_medium_030.txt | AC | 26 ms | 2816 KB |
10_medium_031.txt | AC | 25 ms | 2816 KB |
10_medium_032.txt | AC | 25 ms | 2816 KB |
10_medium_033.txt | AC | 25 ms | 2816 KB |
10_medium_034.txt | AC | 25 ms | 2816 KB |
10_medium_035.txt | AC | 24 ms | 2816 KB |
10_medium_036.txt | AC | 24 ms | 2816 KB |
10_medium_037.txt | AC | 24 ms | 2816 KB |
10_medium_038.txt | AC | 23 ms | 2816 KB |
10_medium_039.txt | AC | 23 ms | 2816 KB |
10_medium_040.txt | AC | 24 ms | 2816 KB |
10_medium_041.txt | AC | 23 ms | 2816 KB |
10_medium_042.txt | AC | 24 ms | 2816 KB |
10_medium_043.txt | AC | 24 ms | 2816 KB |
10_medium_044.txt | AC | 23 ms | 2816 KB |
10_medium_045.txt | AC | 23 ms | 2816 KB |
10_medium_046.txt | AC | 24 ms | 2816 KB |
10_medium_047.txt | AC | 23 ms | 2816 KB |
10_medium_048.txt | AC | 23 ms | 2816 KB |
10_medium_049.txt | AC | 23 ms | 2816 KB |
10_medium_050.txt | AC | 25 ms | 2816 KB |
10_medium_051.txt | AC | 23 ms | 2816 KB |
10_medium_088.txt | AC | 36 ms | 2816 KB |
10_medium_089.txt | AC | 35 ms | 2816 KB |
10_medium_090.txt | AC | 36 ms | 2816 KB |
10_medium_091.txt | AC | 37 ms | 2816 KB |
10_medium_092.txt | AC | 38 ms | 2816 KB |
10_medium_093.txt | AC | 35 ms | 2816 KB |
10_medium_094.txt | AC | 37 ms | 2816 KB |
10_medium_095.txt | AC | 34 ms | 2816 KB |
10_medium_096.txt | AC | 36 ms | 2816 KB |
10_medium_097.txt | AC | 35 ms | 2816 KB |
10_medium_118.txt | AC | 40 ms | 2816 KB |
10_medium_119.txt | AC | 35 ms | 2816 KB |
10_medium_120.txt | AC | 37 ms | 2816 KB |
10_medium_121.txt | AC | 38 ms | 2816 KB |
10_medium_122.txt | AC | 40 ms | 2816 KB |
10_medium_123.txt | AC | 40 ms | 2816 KB |
10_medium_124.txt | AC | 40 ms | 2816 KB |
10_medium_125.txt | AC | 40 ms | 2816 KB |
10_medium_126.txt | AC | 40 ms | 2816 KB |
10_medium_127.txt | AC | 40 ms | 2816 KB |
20_large_052.txt | TLE | 2105 ms | 24264 KB |
20_large_053.txt | TLE | 2105 ms | 21900 KB |
20_large_054.txt | TLE | 2105 ms | 21720 KB |
20_large_055.txt | TLE | 2105 ms | 21816 KB |
20_large_056.txt | TLE | 2083 ms | 23224 KB |
20_large_057.txt | TLE | 2018 ms | 23736 KB |
20_large_058.txt | AC | 1986 ms | 23992 KB |
20_large_059.txt | AC | 1851 ms | 21640 KB |
20_large_060.txt | AC | 1994 ms | 24120 KB |
20_large_061.txt | AC | 1988 ms | 24120 KB |
20_large_062.txt | AC | 1988 ms | 24120 KB |
20_large_063.txt | AC | 1986 ms | 24248 KB |
20_large_064.txt | AC | 1994 ms | 24248 KB |
20_large_065.txt | AC | 1979 ms | 24248 KB |
20_large_066.txt | AC | 1968 ms | 24248 KB |
20_large_067.txt | AC | 1816 ms | 21768 KB |
20_large_068.txt | AC | 1957 ms | 24248 KB |
20_large_069.txt | AC | 1961 ms | 24248 KB |
20_large_070.txt | AC | 1817 ms | 22536 KB |
20_large_071.txt | AC | 1963 ms | 24248 KB |
20_large_072.txt | AC | 1808 ms | 22792 KB |
20_large_073.txt | AC | 1807 ms | 22920 KB |
20_large_074.txt | AC | 1940 ms | 24248 KB |
20_large_075.txt | AC | 1783 ms | 23176 KB |
20_large_076.txt | AC | 1782 ms | 23176 KB |
20_large_077.txt | AC | 1783 ms | 23304 KB |
20_large_098.txt | TLE | 2104 ms | 24220 KB |
20_large_099.txt | TLE | 2105 ms | 24172 KB |
20_large_100.txt | TLE | 2105 ms | 24220 KB |
20_large_101.txt | TLE | 2105 ms | 24220 KB |
20_large_102.txt | TLE | 2105 ms | 24220 KB |
20_large_103.txt | TLE | 2105 ms | 24220 KB |
20_large_104.txt | TLE | 2105 ms | 24220 KB |
20_large_105.txt | TLE | 2105 ms | 24220 KB |
20_large_106.txt | TLE | 2105 ms | 24248 KB |
20_large_107.txt | TLE | 2104 ms | 24220 KB |
20_large_128.txt | TLE | 2105 ms | 24220 KB |
20_large_129.txt | TLE | 2105 ms | 24220 KB |
20_large_130.txt | TLE | 2105 ms | 24120 KB |
20_large_131.txt | TLE | 2105 ms | 24172 KB |
20_large_132.txt | TLE | 2105 ms | 24300 KB |
20_large_133.txt | TLE | 2105 ms | 24248 KB |
20_large_134.txt | TLE | 2105 ms | 24220 KB |
20_large_135.txt | TLE | 2105 ms | 24092 KB |
20_large_136.txt | TLE | 2105 ms | 24220 KB |
20_large_137.txt | TLE | 2105 ms | 24248 KB |