제출 #99226

#제출 시각아이디문제언어결과실행 시간메모리
99226dsg213Palinilap (COI16_palinilap)C++14
0 / 100
107 ms32000 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define ll long long #define ull unsigned ll #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> const int mod=1000000007,mxn=1000010; string s; int n; ull p=313; ull hap[mxn]; ull hal[mxn]; ull pot[mxn]; ull gethp(int left,int right){ return hap[right]-hap[left-1]*pot[right-left+1]; } ull gethl(int left,int right){ return hal[left]-hal[right+1]*pot[right-left+1]; } ll acc[mxn]; ll ilz[mxn]; ll wie[mxn][26]; ll ans; void liczsro(int x){ int mn=1; int mx=min(x,n-x+1); //cout <<mx <<" "; while(mn<mx){ int sr=(mn+mx+1)/2; if(gethp(x-sr+1,x)==gethl(x,x+sr-1)){ mn=sr; } else{ mx=sr-1; } } //cout <<mn <<" "; acc[x-mn]+=1; acc[x]-=2; acc[x+mn]+=1; int baz=mn; ans+=baz; if(baz==min(x,n-x+1)){ //cout <<"0\n"; return; } mx=min(x,n-x+1); mn=baz+1; while(mn<mx){ int sr=(mn+mx+1)/2; if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+1,x+sr-1)){ mn=sr; } else{ mx=sr-1; } } int dod=mn-baz; //cout <<baz <<" "<<dod <<"\n"; char c1=s[x-baz-1]-'a'; char c2=s[x+baz-1]-'a'; wie[x-baz][c2]+=dod; wie[x+baz][c1]+=dod; //cout <<x <<" " <<baz <<" " <<c2+'a' <<"\n"; } void liczd(int x){ int mn=0; int mx=min(x,n-x); while(mn<mx){ int sr=(mn+mx+1)/2; if(gethp(x-sr+1,x)==gethl(x+1,x+sr)){ mn=sr; } else{ mx=sr-1; } } //cout <<mn <<" "; acc[x-mn]+=1; acc[x]-=1; acc[x+1]-=1; acc[x+mn+1]+=1; int baz=mn; ans+=baz; if(baz==min(x,n-x)){ //cout <<"0 "; return; } mx=min(x,n-x); mn=baz+1; //cout <<mx <<" "; while(mn<mx){ int sr=(mn+mx+1)/2; if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+2,x+sr)){ mn=sr; } else{ mx=sr-1; } } int dod=mn-baz; //cout <<dod <<" "; char c1=s[x-baz-1]-'a'; char c2=s[x+baz]-'a'; wie[x-baz][c2]+=dod; wie[x+baz+1][c1]+=dod; //cout <<x-baz <<" " <<'a'+c2 <<"\n"; } void pro(){ ll pr=0; ll val=0; for(int i=0;i<=n;i++){ ilz[i]=val; pr+=acc[i]; val+=pr; } } int main(){ cin >>s; n=s.size(); pot[0]=1; for(ull i=1;i<=mxn-10;i++){ pot[i]=pot[i-1]*p; } for(int i=0;i<n;i++){ hap[i+1]=hap[i]*p+s[i]; } for(int i=n;i>0;i--){ hal[i]=hal[i+1]*p+s[i-1]; } /*while(1){ int a,b; cin >>a >>b; cout <<gethp(a,b) <<"\n"; cout <<gethl(a,b) <<"\n"; }*/ for(int i=1;i<=n;i++){ liczsro(i); } //cout <<"\n"; for(int i=1;i<n;i++){ liczd(i); } //cout <<"\n"; pro(); //cout <<"\n"; /*for(int i=0;i<=n;i++){ cout <<acc[i] <<" "; } cout <<"\n"; */ /*for(int i=0;i<=n;i++){ cout <<ilz[i] <<" "; }*/ //cout <<ans<<"\n"; ll wyn=ans; for(int i=1;i<=n;i++){ //cout <<ilz[i] <<" "; for(int j=0;j<26;j++){ wyn=max(wyn,ans+wie[i][j]-ilz[i]+1); } } //cout <<"\n"; /*for(int i=1;i<=n;i++){ ll x=0; for(int j=0;j<26;j++){ x=max(x,wie[i][j]); } cout <<x<<" "; } cout <<"\n";*/ cout <<wyn; }

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

palinilap.cpp: In function 'void liczsro(int)':
palinilap.cpp:67:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:68:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz][c1]+=dod;
               ^
palinilap.cpp: In function 'void liczd(int)':
palinilap.cpp:111:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:112:17: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz+1][c1]+=dod;
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...