Submission #1481399
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 | Ruby (2.3.3) |
Score | 0 |
Code Size | 1031 Byte |
Status | RE |
Exec Time | 7 ms |
Memory | 1788 KB |
Compile Error
ruby2.3: no Ruby script found in input (LoadError)
Judge Result
Set Name | Subtask1 | Subtask2 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 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 | RE | 7 ms | 1788 KB |
00_sample_01.txt | RE | 7 ms | 1788 KB |
00_sample_02.txt | RE | 7 ms | 1788 KB |
00_sample_03.txt | RE | 7 ms | 1788 KB |
00_small_000.txt | RE | 7 ms | 1788 KB |
00_small_001.txt | RE | 7 ms | 1788 KB |
00_small_002.txt | RE | 7 ms | 1788 KB |
00_small_003.txt | RE | 7 ms | 1788 KB |
00_small_004.txt | RE | 7 ms | 1788 KB |
00_small_005.txt | RE | 7 ms | 1788 KB |
00_small_006.txt | RE | 7 ms | 1788 KB |
00_small_007.txt | RE | 7 ms | 1788 KB |
00_small_008.txt | RE | 7 ms | 1788 KB |
00_small_009.txt | RE | 7 ms | 1788 KB |
00_small_010.txt | RE | 7 ms | 1788 KB |
00_small_011.txt | RE | 7 ms | 1788 KB |
00_small_012.txt | RE | 7 ms | 1788 KB |
00_small_013.txt | RE | 7 ms | 1788 KB |
00_small_014.txt | RE | 7 ms | 1788 KB |
00_small_015.txt | RE | 7 ms | 1788 KB |
00_small_016.txt | RE | 7 ms | 1788 KB |
00_small_017.txt | RE | 7 ms | 1788 KB |
00_small_018.txt | RE | 7 ms | 1788 KB |
00_small_019.txt | RE | 7 ms | 1788 KB |
00_small_020.txt | RE | 7 ms | 1788 KB |
00_small_021.txt | RE | 7 ms | 1788 KB |
00_small_022.txt | RE | 7 ms | 1788 KB |
00_small_023.txt | RE | 7 ms | 1788 KB |
00_small_024.txt | RE | 7 ms | 1788 KB |
00_small_025.txt | RE | 7 ms | 1788 KB |
00_small_078.txt | RE | 7 ms | 1788 KB |
00_small_079.txt | RE | 7 ms | 1788 KB |
00_small_080.txt | RE | 7 ms | 1788 KB |
00_small_081.txt | RE | 7 ms | 1788 KB |
00_small_082.txt | RE | 7 ms | 1788 KB |
00_small_083.txt | RE | 7 ms | 1788 KB |
00_small_084.txt | RE | 7 ms | 1788 KB |
00_small_085.txt | RE | 7 ms | 1788 KB |
00_small_086.txt | RE | 7 ms | 1788 KB |
00_small_087.txt | RE | 7 ms | 1788 KB |
00_small_108.txt | RE | 7 ms | 1788 KB |
00_small_109.txt | RE | 7 ms | 1788 KB |
00_small_110.txt | RE | 7 ms | 1788 KB |
00_small_111.txt | RE | 7 ms | 1788 KB |
00_small_112.txt | RE | 7 ms | 1788 KB |
00_small_113.txt | RE | 7 ms | 1788 KB |
00_small_114.txt | RE | 7 ms | 1788 KB |
00_small_115.txt | RE | 7 ms | 1788 KB |
00_small_116.txt | RE | 7 ms | 1788 KB |
00_small_117.txt | RE | 7 ms | 1788 KB |
00_teuchi_00.txt | RE | 7 ms | 1788 KB |
10_medium_026.txt | RE | 7 ms | 1788 KB |
10_medium_027.txt | RE | 7 ms | 1788 KB |
10_medium_028.txt | RE | 7 ms | 1788 KB |
10_medium_029.txt | RE | 7 ms | 1788 KB |
10_medium_030.txt | RE | 7 ms | 1788 KB |
10_medium_031.txt | RE | 7 ms | 1788 KB |
10_medium_032.txt | RE | 7 ms | 1788 KB |
10_medium_033.txt | RE | 7 ms | 1788 KB |
10_medium_034.txt | RE | 7 ms | 1788 KB |
10_medium_035.txt | RE | 7 ms | 1788 KB |
10_medium_036.txt | RE | 7 ms | 1788 KB |
10_medium_037.txt | RE | 7 ms | 1788 KB |
10_medium_038.txt | RE | 7 ms | 1788 KB |
10_medium_039.txt | RE | 7 ms | 1788 KB |
10_medium_040.txt | RE | 7 ms | 1788 KB |
10_medium_041.txt | RE | 7 ms | 1788 KB |
10_medium_042.txt | RE | 7 ms | 1788 KB |
10_medium_043.txt | RE | 7 ms | 1788 KB |
10_medium_044.txt | RE | 7 ms | 1788 KB |
10_medium_045.txt | RE | 7 ms | 1788 KB |
10_medium_046.txt | RE | 7 ms | 1788 KB |
10_medium_047.txt | RE | 7 ms | 1788 KB |
10_medium_048.txt | RE | 7 ms | 1788 KB |
10_medium_049.txt | RE | 7 ms | 1788 KB |
10_medium_050.txt | RE | 7 ms | 1788 KB |
10_medium_051.txt | RE | 6 ms | 1788 KB |
10_medium_088.txt | RE | 7 ms | 1788 KB |
10_medium_089.txt | RE | 7 ms | 1788 KB |
10_medium_090.txt | RE | 7 ms | 1788 KB |
10_medium_091.txt | RE | 7 ms | 1788 KB |
10_medium_092.txt | RE | 7 ms | 1788 KB |
10_medium_093.txt | RE | 7 ms | 1788 KB |
10_medium_094.txt | RE | 7 ms | 1788 KB |
10_medium_095.txt | RE | 7 ms | 1788 KB |
10_medium_096.txt | RE | 7 ms | 1788 KB |
10_medium_097.txt | RE | 7 ms | 1788 KB |
10_medium_118.txt | RE | 7 ms | 1788 KB |
10_medium_119.txt | RE | 7 ms | 1788 KB |
10_medium_120.txt | RE | 7 ms | 1788 KB |
10_medium_121.txt | RE | 7 ms | 1788 KB |
10_medium_122.txt | RE | 7 ms | 1788 KB |
10_medium_123.txt | RE | 7 ms | 1788 KB |
10_medium_124.txt | RE | 7 ms | 1788 KB |
10_medium_125.txt | RE | 7 ms | 1788 KB |
10_medium_126.txt | RE | 7 ms | 1788 KB |
10_medium_127.txt | RE | 7 ms | 1788 KB |
20_large_052.txt | RE | 7 ms | 1788 KB |
20_large_053.txt | RE | 7 ms | 1788 KB |
20_large_054.txt | RE | 7 ms | 1788 KB |
20_large_055.txt | RE | 7 ms | 1788 KB |
20_large_056.txt | RE | 7 ms | 1788 KB |
20_large_057.txt | RE | 7 ms | 1788 KB |
20_large_058.txt | RE | 7 ms | 1788 KB |
20_large_059.txt | RE | 7 ms | 1788 KB |
20_large_060.txt | RE | 7 ms | 1788 KB |
20_large_061.txt | RE | 7 ms | 1788 KB |
20_large_062.txt | RE | 7 ms | 1788 KB |
20_large_063.txt | RE | 7 ms | 1788 KB |
20_large_064.txt | RE | 7 ms | 1788 KB |
20_large_065.txt | RE | 7 ms | 1788 KB |
20_large_066.txt | RE | 7 ms | 1788 KB |
20_large_067.txt | RE | 7 ms | 1788 KB |
20_large_068.txt | RE | 7 ms | 1788 KB |
20_large_069.txt | RE | 7 ms | 1788 KB |
20_large_070.txt | RE | 6 ms | 1788 KB |
20_large_071.txt | RE | 7 ms | 1788 KB |
20_large_072.txt | RE | 7 ms | 1788 KB |
20_large_073.txt | RE | 7 ms | 1788 KB |
20_large_074.txt | RE | 7 ms | 1788 KB |
20_large_075.txt | RE | 7 ms | 1788 KB |
20_large_076.txt | RE | 7 ms | 1788 KB |
20_large_077.txt | RE | 7 ms | 1788 KB |
20_large_098.txt | RE | 7 ms | 1788 KB |
20_large_099.txt | RE | 7 ms | 1788 KB |
20_large_100.txt | RE | 7 ms | 1788 KB |
20_large_101.txt | RE | 7 ms | 1788 KB |
20_large_102.txt | RE | 7 ms | 1788 KB |
20_large_103.txt | RE | 7 ms | 1788 KB |
20_large_104.txt | RE | 7 ms | 1788 KB |
20_large_105.txt | RE | 7 ms | 1788 KB |
20_large_106.txt | RE | 7 ms | 1788 KB |
20_large_107.txt | RE | 7 ms | 1788 KB |
20_large_128.txt | RE | 7 ms | 1788 KB |
20_large_129.txt | RE | 7 ms | 1788 KB |
20_large_130.txt | RE | 7 ms | 1788 KB |
20_large_131.txt | RE | 7 ms | 1788 KB |
20_large_132.txt | RE | 7 ms | 1788 KB |
20_large_133.txt | RE | 7 ms | 1788 KB |
20_large_134.txt | RE | 7 ms | 1788 KB |
20_large_135.txt | RE | 7 ms | 1788 KB |
20_large_136.txt | RE | 7 ms | 1788 KB |
20_large_137.txt | RE | 7 ms | 1788 KB |