Submission #1165786
Source Code Expand
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<vector> #define N 100005 #define M 6000005 #define ls tree[t].l #define rs tree[t].r #define mid ((l+r)>>1) #define pb push_back using namespace std; long long ans; int n,F,Rank[N*2],G[N],sa[N],High[N],i,j,k,m,sum[N],trk[N],p,tot,bl[N]; char s[N*2]; void Sort() { int i; memset(sum,0,sizeof(sum)); for (i=1;i<=n;++i) sum[Rank[i+j]]++; for (i=1;i<N;++i) sum[i]+=sum[i-1]; for (i=n;i;--i) G[sum[Rank[i+j]]--]=i; memset(sum,0,sizeof(sum)); for (i=1;i<=n;++i) sum[Rank[i]]++; for (i=1;i<N;++i) sum[i]+=sum[i-1]; for (i=n;i;--i) sa[sum[Rank[G[i]]]--]=G[i]; } void get_sa() { for (i=1;i<=n;++i) trk[i]=s[i]; for (i=1;i<=n;++i) sum[trk[i]]++; for (i=1;i<N;++i) sum[i]+=sum[i-1]; for (i=n;i;--i) sa[sum[trk[i]]--]=i; for (Rank[sa[1]]=1,p=1,i=2;i<=n;++i) { if (trk[sa[i-1]]!=trk[sa[i]]) ++p; Rank[sa[i]]=p; } for (j=1;j<=n;j<<=1) { Sort(); trk[sa[1]]=1; for (i=2,p=1;i<=n;++i) { if (Rank[sa[i]]!=Rank[sa[i-1]]||Rank[sa[i]+j]!=Rank[sa[i-1]+j]) ++p; trk[sa[i]]=p; } for (i=1;i<=n;++i) Rank[i]=trk[i]; } } void get_high() { int i,j; for (i=1,j=0;i<=n;++i) { if (Rank[i]==1) continue; while (s[i+j]==s[sa[Rank[i]-1]+j]) ++j; High[Rank[i]]=j; if (j) --j; } } inline int read() { int x,f; char c; while (c=getchar(),(c<'0'||c>'9')&&c!='-'); if (c=='-') f=1,c=getchar(); else f=0; x=c-'0'; while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0'; return f?-x:x; } int main() { scanf("%s",s+1); n=strlen(s+1); get_sa(); get_high(); memset(sum,0,sizeof(sum)); for (i=1;i<=n;++i) sum[High[i]]++; for (i=1;i<=n;++i) sum[i]+=sum[i-1]; int ans=0; for (i=1;i<=n;++i) ans=max(ans,sum[i-1]-(i-1)); printf("%d\n",ans); }
Submission Info
Submission Time | |
---|---|
Task | G - Exam |
User | qiaoranliqu |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1862 Byte |
Status | AC |
Exec Time | 65 ms |
Memory | 2816 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:85:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",s+1); ^
Judge Result
Set Name | Subtask1 | Subtask2 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 30 / 30 | 140 / 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 | 3 ms | 640 KB |
00_sample_01.txt | AC | 4 ms | 640 KB |
00_sample_02.txt | AC | 4 ms | 640 KB |
00_sample_03.txt | AC | 5 ms | 640 KB |
00_small_000.txt | AC | 5 ms | 640 KB |
00_small_001.txt | AC | 5 ms | 640 KB |
00_small_002.txt | AC | 5 ms | 640 KB |
00_small_003.txt | AC | 5 ms | 640 KB |
00_small_004.txt | AC | 5 ms | 640 KB |
00_small_005.txt | AC | 5 ms | 640 KB |
00_small_006.txt | AC | 5 ms | 640 KB |
00_small_007.txt | AC | 5 ms | 640 KB |
00_small_008.txt | AC | 5 ms | 640 KB |
00_small_009.txt | AC | 5 ms | 640 KB |
00_small_010.txt | AC | 5 ms | 640 KB |
00_small_011.txt | AC | 5 ms | 640 KB |
00_small_012.txt | AC | 5 ms | 640 KB |
00_small_013.txt | AC | 5 ms | 640 KB |
00_small_014.txt | AC | 5 ms | 640 KB |
00_small_015.txt | AC | 5 ms | 640 KB |
00_small_016.txt | AC | 5 ms | 640 KB |
00_small_017.txt | AC | 5 ms | 640 KB |
00_small_018.txt | AC | 5 ms | 640 KB |
00_small_019.txt | AC | 5 ms | 640 KB |
00_small_020.txt | AC | 5 ms | 640 KB |
00_small_021.txt | AC | 5 ms | 640 KB |
00_small_022.txt | AC | 5 ms | 640 KB |
00_small_023.txt | AC | 5 ms | 640 KB |
00_small_024.txt | AC | 5 ms | 640 KB |
00_small_025.txt | AC | 5 ms | 640 KB |
00_small_078.txt | AC | 5 ms | 640 KB |
00_small_079.txt | AC | 5 ms | 640 KB |
00_small_080.txt | AC | 5 ms | 640 KB |
00_small_081.txt | AC | 5 ms | 640 KB |
00_small_082.txt | AC | 5 ms | 640 KB |
00_small_083.txt | AC | 5 ms | 640 KB |
00_small_084.txt | AC | 5 ms | 640 KB |
00_small_085.txt | AC | 5 ms | 640 KB |
00_small_086.txt | AC | 5 ms | 640 KB |
00_small_087.txt | AC | 5 ms | 640 KB |
00_small_108.txt | AC | 5 ms | 640 KB |
00_small_109.txt | AC | 5 ms | 640 KB |
00_small_110.txt | AC | 5 ms | 640 KB |
00_small_111.txt | AC | 5 ms | 640 KB |
00_small_112.txt | AC | 5 ms | 640 KB |
00_small_113.txt | AC | 5 ms | 640 KB |
00_small_114.txt | AC | 5 ms | 640 KB |
00_small_115.txt | AC | 5 ms | 640 KB |
00_small_116.txt | AC | 5 ms | 640 KB |
00_small_117.txt | AC | 5 ms | 640 KB |
00_teuchi_00.txt | AC | 2 ms | 640 KB |
10_medium_026.txt | AC | 7 ms | 640 KB |
10_medium_027.txt | AC | 7 ms | 640 KB |
10_medium_028.txt | AC | 7 ms | 640 KB |
10_medium_029.txt | AC | 7 ms | 640 KB |
10_medium_030.txt | AC | 7 ms | 640 KB |
10_medium_031.txt | AC | 7 ms | 640 KB |
10_medium_032.txt | AC | 7 ms | 640 KB |
10_medium_033.txt | AC | 7 ms | 640 KB |
10_medium_034.txt | AC | 7 ms | 640 KB |
10_medium_035.txt | AC | 7 ms | 640 KB |
10_medium_036.txt | AC | 7 ms | 640 KB |
10_medium_037.txt | AC | 7 ms | 640 KB |
10_medium_038.txt | AC | 7 ms | 640 KB |
10_medium_039.txt | AC | 7 ms | 640 KB |
10_medium_040.txt | AC | 7 ms | 640 KB |
10_medium_041.txt | AC | 7 ms | 640 KB |
10_medium_042.txt | AC | 7 ms | 640 KB |
10_medium_043.txt | AC | 7 ms | 640 KB |
10_medium_044.txt | AC | 7 ms | 640 KB |
10_medium_045.txt | AC | 7 ms | 640 KB |
10_medium_046.txt | AC | 7 ms | 640 KB |
10_medium_047.txt | AC | 7 ms | 640 KB |
10_medium_048.txt | AC | 7 ms | 640 KB |
10_medium_049.txt | AC | 7 ms | 640 KB |
10_medium_050.txt | AC | 7 ms | 640 KB |
10_medium_051.txt | AC | 7 ms | 640 KB |
10_medium_088.txt | AC | 7 ms | 640 KB |
10_medium_089.txt | AC | 7 ms | 640 KB |
10_medium_090.txt | AC | 7 ms | 640 KB |
10_medium_091.txt | AC | 7 ms | 640 KB |
10_medium_092.txt | AC | 7 ms | 640 KB |
10_medium_093.txt | AC | 7 ms | 640 KB |
10_medium_094.txt | AC | 7 ms | 640 KB |
10_medium_095.txt | AC | 7 ms | 640 KB |
10_medium_096.txt | AC | 7 ms | 640 KB |
10_medium_097.txt | AC | 7 ms | 640 KB |
10_medium_118.txt | AC | 7 ms | 640 KB |
10_medium_119.txt | AC | 7 ms | 640 KB |
10_medium_120.txt | AC | 7 ms | 640 KB |
10_medium_121.txt | AC | 7 ms | 640 KB |
10_medium_122.txt | AC | 7 ms | 640 KB |
10_medium_123.txt | AC | 7 ms | 640 KB |
10_medium_124.txt | AC | 7 ms | 640 KB |
10_medium_125.txt | AC | 7 ms | 640 KB |
10_medium_126.txt | AC | 7 ms | 640 KB |
10_medium_127.txt | AC | 7 ms | 640 KB |
20_large_052.txt | AC | 30 ms | 2688 KB |
20_large_053.txt | AC | 57 ms | 2688 KB |
20_large_054.txt | AC | 61 ms | 2688 KB |
20_large_055.txt | AC | 61 ms | 2688 KB |
20_large_056.txt | AC | 63 ms | 2688 KB |
20_large_057.txt | AC | 63 ms | 2688 KB |
20_large_058.txt | AC | 63 ms | 2688 KB |
20_large_059.txt | AC | 61 ms | 2688 KB |
20_large_060.txt | AC | 64 ms | 2688 KB |
20_large_061.txt | AC | 64 ms | 2688 KB |
20_large_062.txt | AC | 64 ms | 2688 KB |
20_large_063.txt | AC | 64 ms | 2688 KB |
20_large_064.txt | AC | 64 ms | 2688 KB |
20_large_065.txt | AC | 65 ms | 2688 KB |
20_large_066.txt | AC | 65 ms | 2688 KB |
20_large_067.txt | AC | 63 ms | 2688 KB |
20_large_068.txt | AC | 65 ms | 2688 KB |
20_large_069.txt | AC | 65 ms | 2688 KB |
20_large_070.txt | AC | 65 ms | 2688 KB |
20_large_071.txt | AC | 64 ms | 2688 KB |
20_large_072.txt | AC | 65 ms | 2688 KB |
20_large_073.txt | AC | 65 ms | 2816 KB |
20_large_074.txt | AC | 65 ms | 2688 KB |
20_large_075.txt | AC | 64 ms | 2688 KB |
20_large_076.txt | AC | 65 ms | 2688 KB |
20_large_077.txt | AC | 65 ms | 2688 KB |
20_large_098.txt | AC | 58 ms | 2688 KB |
20_large_099.txt | AC | 56 ms | 2688 KB |
20_large_100.txt | AC | 59 ms | 2688 KB |
20_large_101.txt | AC | 60 ms | 2688 KB |
20_large_102.txt | AC | 59 ms | 2688 KB |
20_large_103.txt | AC | 58 ms | 2688 KB |
20_large_104.txt | AC | 59 ms | 2688 KB |
20_large_105.txt | AC | 60 ms | 2688 KB |
20_large_106.txt | AC | 61 ms | 2688 KB |
20_large_107.txt | AC | 57 ms | 2688 KB |
20_large_128.txt | AC | 54 ms | 2688 KB |
20_large_129.txt | AC | 52 ms | 2688 KB |
20_large_130.txt | AC | 50 ms | 2688 KB |
20_large_131.txt | AC | 50 ms | 2688 KB |
20_large_132.txt | AC | 54 ms | 2688 KB |
20_large_133.txt | AC | 56 ms | 2688 KB |
20_large_134.txt | AC | 55 ms | 2688 KB |
20_large_135.txt | AC | 52 ms | 2688 KB |
20_large_136.txt | AC | 53 ms | 2688 KB |
20_large_137.txt | AC | 58 ms | 2688 KB |