Submission #2211777
Source Code Expand
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<map> #include<set> #include<utility> #include<cmath> #include<cstring> #include<queue> #include<cstdio> #include<sstream> #include<iomanip> #define loop(i,a,b) for(int i=a;i<b;i++) #define rep(i,a) loop(i,0,a) #define pb push_back #define mp make_pair #define all(in) in.begin(),in.end() #define shosu(x) fixed<<setprecision(x) using namespace std; //kaewasuretyuui typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<vp> vvp; typedef pair<int,pii> pip; typedef vector<pip>vip; const double PI=acos(-1); const double EPS=1e-8; const int inf=1e8; ll MOD1=134832894; ll MOD2=183489237; ll x1=52452452; ll x2=34567343; vector<ll>hash1,hash2,X1,X2; int n; int f(int i){ set<pair<ll,ll> >se; rep(j,n-i){ ll a1=(hash1[i+j+1]-hash1[j]+MOD1)%MOD1*X1[n-(i+j+1)]%MOD1; ll a2=(hash2[i+j+1]-hash2[j]+MOD2)%MOD2*X2[n-(i+j+1)]%MOD2; se.insert(pair<ll,ll>(a1,a2)); } return se.size(); } int main(){ string s; cin>>s; n=s.size(); X1=X2=vector<ll>(n+1); X1[0]=X2[0]=1; rep(i,n){ X1[i+1]=(X1[i]*x1)%MOD1; X2[i+1]=(X2[i]*x2)%MOD2; } hash1=hash2=vector<ll>(n+1); rep(i,n){ hash1[i+1]=(s[i]-'a')*X1[i+1]; hash2[i+1]=(s[i]-'a')*X2[i+1]; } rep(i,n){ hash1[i+1]=(hash1[i+1]+hash1[i])%MOD1; hash2[i+1]=(hash2[i+1]+hash2[i])%MOD2; } // rep(i,n){ int l=0,r=n; while(r-l>2){ int h1=l+(r-l)/3,h2=l+(r-l)/3*2; // cout<<l<<" "<<h1<<" "<<h2<<" "<<r<<endl; int H1=f(h1),H2=f(h2); // cout<<H1<<" "<<H2<<endl; if(H1>H2)r=h2; else l=h1; } int out=0; loop(i,l,r)out=max(out,f(i)); cout<<out<<endl; }
Submission Info
Submission Time | |
---|---|
Task | H - WAAAAAAAAAAAAALL |
User | vjudge5 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1688 Byte |
Status | WA |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 30 | 0 / 140 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt |
Subtask2 | 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt |
All | 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt, 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt, 02_100_min.txt, 02_101_min.txt, 02_102_max.txt, 02_103_max.txt, 02_104_max.txt, 02_105_max.txt, 02_106_max.txt, 02_73_random.txt, 02_74_random.txt, 02_75_random.txt, 02_76_random.txt, 02_77_random.txt, 02_78_random.txt, 02_79_random.txt, 02_80_random.txt, 02_81_random.txt, 02_82_random.txt, 02_83_random.txt, 02_84_random.txt, 02_85_random.txt, 02_86_random.txt, 02_87_random.txt, 02_88_random.txt, 02_89_random.txt, 02_90_random.txt, 02_91_random.txt, 02_92_random.txt, 02_93_freedom.txt, 02_94_freedom.txt, 02_95_freedom.txt, 02_96_full.txt, 02_97_full.txt, 02_98_full.txt, 02_99_min.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_00_sample.txt | WA | 1 ms | 256 KB |
00_01_sample.txt | WA | 1 ms | 256 KB |
00_02_sample.txt | WA | 1 ms | 256 KB |
00_03_random.txt | WA | 1 ms | 256 KB |
00_04_random.txt | WA | 1 ms | 256 KB |
00_05_random.txt | WA | 1 ms | 256 KB |
00_06_random.txt | WA | 1 ms | 256 KB |
00_07_random.txt | WA | 1 ms | 256 KB |
00_08_random.txt | WA | 1 ms | 256 KB |
00_09_random.txt | WA | 1 ms | 256 KB |
00_10_random.txt | WA | 1 ms | 256 KB |
00_11_random.txt | WA | 1 ms | 256 KB |
00_12_random.txt | WA | 1 ms | 256 KB |
00_13_random.txt | WA | 1 ms | 256 KB |
00_14_random.txt | WA | 1 ms | 256 KB |
00_15_random.txt | WA | 1 ms | 256 KB |
00_16_random.txt | WA | 1 ms | 256 KB |
00_17_random.txt | WA | 1 ms | 256 KB |
00_18_random.txt | WA | 1 ms | 256 KB |
00_19_random.txt | WA | 1 ms | 256 KB |
00_20_random.txt | WA | 1 ms | 256 KB |
00_21_random.txt | WA | 1 ms | 256 KB |
00_22_random.txt | WA | 1 ms | 256 KB |
00_23_freedom.txt | WA | 1 ms | 256 KB |
00_24_freedom.txt | WA | 1 ms | 256 KB |
00_25_freedom.txt | WA | 1 ms | 256 KB |
00_26_full.txt | WA | 1 ms | 256 KB |
00_27_full.txt | WA | 1 ms | 256 KB |
00_28_full.txt | WA | 1 ms | 256 KB |
00_29_min.txt | WA | 1 ms | 256 KB |
00_30_min.txt | WA | 1 ms | 256 KB |
00_31_min.txt | WA | 1 ms | 256 KB |
00_32_max.txt | WA | 1 ms | 256 KB |
00_33_max.txt | WA | 1 ms | 256 KB |
00_34_max.txt | WA | 1 ms | 256 KB |
00_35_max.txt | WA | 1 ms | 256 KB |
00_36_max.txt | WA | 1 ms | 256 KB |
01_37_sample.txt | WA | 1 ms | 256 KB |
01_38_sample.txt | WA | 1 ms | 256 KB |
01_39_random.txt | WA | 1 ms | 256 KB |
01_40_random.txt | WA | 1 ms | 256 KB |
01_41_random.txt | WA | 1 ms | 256 KB |
01_42_random.txt | WA | 1 ms | 256 KB |
01_43_random.txt | WA | 1 ms | 256 KB |
01_44_random.txt | WA | 1 ms | 256 KB |
01_45_random.txt | WA | 1 ms | 256 KB |
01_46_random.txt | WA | 1 ms | 256 KB |
01_47_random.txt | WA | 1 ms | 256 KB |
01_48_random.txt | WA | 1 ms | 256 KB |
01_49_random.txt | WA | 1 ms | 256 KB |
01_50_random.txt | WA | 1 ms | 256 KB |
01_51_random.txt | WA | 1 ms | 256 KB |
01_52_random.txt | WA | 1 ms | 256 KB |
01_53_random.txt | WA | 1 ms | 256 KB |
01_54_random.txt | WA | 1 ms | 256 KB |
01_55_random.txt | WA | 1 ms | 256 KB |
01_56_random.txt | WA | 1 ms | 256 KB |
01_57_random.txt | WA | 1 ms | 256 KB |
01_58_random.txt | WA | 1 ms | 256 KB |
01_59_freedom.txt | WA | 1 ms | 256 KB |
01_60_freedom.txt | WA | 1 ms | 256 KB |
01_61_freedom.txt | WA | 1 ms | 256 KB |
01_62_full.txt | WA | 1 ms | 256 KB |
01_63_full.txt | WA | 1 ms | 256 KB |
01_64_full.txt | WA | 1 ms | 256 KB |
01_65_min.txt | WA | 1 ms | 256 KB |
01_66_min.txt | WA | 1 ms | 256 KB |
01_67_min.txt | WA | 1 ms | 256 KB |
01_68_max.txt | WA | 1 ms | 256 KB |
01_69_max.txt | WA | 1 ms | 256 KB |
01_70_max.txt | WA | 1 ms | 256 KB |
01_71_max.txt | WA | 1 ms | 256 KB |
01_72_max.txt | WA | 1 ms | 256 KB |
02_100_min.txt | WA | 1 ms | 256 KB |
02_101_min.txt | WA | 1 ms | 256 KB |
02_102_max.txt | WA | 1 ms | 256 KB |
02_103_max.txt | WA | 1 ms | 256 KB |
02_104_max.txt | WA | 1 ms | 256 KB |
02_105_max.txt | WA | 1 ms | 256 KB |
02_106_max.txt | WA | 1 ms | 256 KB |
02_73_random.txt | WA | 1 ms | 256 KB |
02_74_random.txt | WA | 1 ms | 256 KB |
02_75_random.txt | WA | 1 ms | 256 KB |
02_76_random.txt | WA | 1 ms | 256 KB |
02_77_random.txt | WA | 1 ms | 256 KB |
02_78_random.txt | WA | 1 ms | 256 KB |
02_79_random.txt | WA | 1 ms | 256 KB |
02_80_random.txt | WA | 1 ms | 256 KB |
02_81_random.txt | WA | 1 ms | 256 KB |
02_82_random.txt | WA | 1 ms | 256 KB |
02_83_random.txt | WA | 1 ms | 256 KB |
02_84_random.txt | WA | 1 ms | 256 KB |
02_85_random.txt | WA | 1 ms | 256 KB |
02_86_random.txt | WA | 1 ms | 256 KB |
02_87_random.txt | WA | 1 ms | 256 KB |
02_88_random.txt | WA | 1 ms | 256 KB |
02_89_random.txt | WA | 1 ms | 256 KB |
02_90_random.txt | WA | 1 ms | 256 KB |
02_91_random.txt | WA | 1 ms | 256 KB |
02_92_random.txt | WA | 1 ms | 256 KB |
02_93_freedom.txt | WA | 1 ms | 256 KB |
02_94_freedom.txt | WA | 1 ms | 256 KB |
02_95_freedom.txt | WA | 1 ms | 256 KB |
02_96_full.txt | WA | 1 ms | 256 KB |
02_97_full.txt | WA | 1 ms | 256 KB |
02_98_full.txt | WA | 1 ms | 256 KB |
02_99_min.txt | WA | 1 ms | 256 KB |