제출 #274842

#제출 시각아이디문제언어결과실행 시간메모리
274842sean9892구간 성분 (KOI15_interval)C++14
31 / 100
1090 ms63864 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include<bits/stdc++.h> using namespace std; using ll=unsigned long long; using pii=pair<ll,ll>; ll ga[1510]; ll ha[1510]; ll gb[1510]; ll hb[1510]; set<pii> s; ll p7[30]; ll p5[30]; const ll mod=9223372036854775783ll; int res=0; int main(void){ ios::sync_with_stdio(0);cin.tie(0); { ll a=1,b=1; for(int i=0;i<26;i++){ p7[i]=a; p5[i]=b; a*=7; b*=5; a%=mod; } } string a,b; cin>>a>>b; if(a.size()>b.size())swap(a,b); ga[0]=gb[0]=ha[0]=hb[0]=0; ga[1]=p7[('z'-a[0])]; ha[1]=p5[(a[0]-'a')^7]; for(int i=1;i<a.size();i++){ ga[i+1]=ga[i]+p7[('z'-a[i])]; if(ga[i+1]>=mod)ga[i+1]%=mod; ha[i+1]=ha[i]+p5[(a[i]-'a')^7]; } gb[1]=p7[('z'-b[0])]; hb[1]=p5[(b[0]-'a')^7]; for(int i=1;i<b.size();i++){ gb[i+1]=gb[i]+p7[('z'-b[i])]; if(gb[i+1]>=mod)gb[i+1]%=mod; hb[i+1]=hb[i]+p5[(b[i]-'a')^7]; } if(10ll*a.size()*a.size()*b.size()<=2e9){ for(int i=1;i<a.size();i++){ for(int j=0;j+res<i;j++){ for(int k=i-j;k<b.size();k++){ if(ha[i]-ha[j]==hb[k]-hb[k-i+j]){ res=max(res,i-j); break; } } } } cout<<res; return 0; } for(int i=(int)a.size()-1;i>0;i--){ for(int j=0;j<i;j++){ ll x=ga[i]-ga[j]; ll y=ha[i]-ha[j]; s.insert(pii(x,y)); } } for(int i=(int)a.size()-1;i>0;i--){ for(int j=0;j+res<i;j++){ ll x=gb[i]-gb[j]; ll y=hb[i]-hb[j]; if(s.find(pii(x,y))!=s.end()){ res=max(res,i-j); break; } } } cout<<res; }

컴파일 시 표준 에러 (stderr) 메시지

interval.cpp: In function 'int main()':
interval.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=1;i<a.size();i++){
      |              ~^~~~~~~~~
interval.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=1;i<b.size();i++){
      |              ~^~~~~~~~~
interval.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=1;i<a.size();i++){
      |               ~^~~~~~~~~
interval.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int k=i-j;k<b.size();k++){
      |                   ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...