fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class S, class T> inline S min_L(S a,T b){
  5.   return a<=b?a:b;
  6. }
  7. template<class T> void malloc1d(T **arr, int x){
  8.   (*arr) = (T*)malloc(x*sizeof(T));
  9. }
  10. template<class T> void free1d(T *arr){
  11.   free(arr);
  12. }
  13. template<class S, class T> inline S chmax(S &a, T b){
  14.   if(a<b){
  15.     a=b;
  16.   }
  17.   return a;
  18. }
  19. template<class T> struct Grid1d{
  20.   T *d, *d_s;
  21.   int *dw, *lf, n, *rg, set_d, set_s, *up;
  22.   void malloc(const int nn){
  23.     n = nn;
  24.     set_s = 0;
  25.     set_d = 0;
  26.     malloc1d(&d, n);
  27.   }
  28.   void free(void){
  29.     free1d(d);
  30.     if(set_s){
  31.       free1d(d_s);
  32.     }
  33.     if(set_d){
  34.       free1d(up);
  35.       free1d(dw);
  36.     }
  37.   }
  38.   T& operator[](int a){
  39.     return d[a];
  40.   }
  41.   void setSum(void){
  42.     int i;
  43.     if(set_s == 0){
  44.       set_s = 1;
  45.       malloc2d(&d_s, n+1);
  46.     }
  47.     d_s[0] = 0;
  48.     for(i=0;i<(n);i++){
  49.       d_s[i+1] = d_s[i] + d[i];
  50.     }
  51.   }
  52.   void setDir(void){
  53.     int i;
  54.     if(set_d == 0){
  55.       set_d = 1;
  56.       malloc1d(&up, n);
  57.       malloc1d(&dw, n);
  58.       lf = dw;
  59.       rg = up;
  60.     }
  61.     lf[0] = 1;
  62.     for(i=(1);i<(n);i++){
  63.       if(d[i]==d[i-1]){
  64.         lf[i] = 1 + lf[i-1];
  65.       }
  66.       else{
  67.         lf[i] = 1 ;
  68.       }
  69.     }
  70.     rg[n-1] = 1;
  71.     for(i=n-2;i>=0;i--){
  72.       if(d[i]==d[i+1]){
  73.         rg[i] = 1 + rg[i+1];
  74.       }
  75.       else{
  76.         rg[i] = 1 ;
  77.       }
  78.     }
  79.   }
  80.   void setDirMatch(const T v){
  81.     int i;
  82.     if(set_d == 0){
  83.       set_d = 1;
  84.       malloc1d(&up, n);
  85.       malloc1d(&dw, n);
  86.       lf = dw;
  87.       rg = up;
  88.     }
  89.     if(d[0]==v){
  90.       lf[0] =1;
  91.     }
  92.     else{
  93.       lf[0] =0;
  94.     }
  95.     for(i=(1);i<(n);i++){
  96.       if(d[i]==v){
  97.         lf[i] =1 + lf[i-1];
  98.       }
  99.       else{
  100.         lf[i] =0;
  101.       }
  102.     }
  103.     if(d[n-1]==v){
  104.       rg[n-1] =1;
  105.     }
  106.     else{
  107.       rg[n-1] =0;
  108.     }
  109.     for(i=n-2;i>=0;i--){
  110.       if(d[i]==v){
  111.         rg[i] =1 + rg[i+1];
  112.       }
  113.       else{
  114.         rg[i] =0;
  115.       }
  116.     }
  117.   }
  118.   inline T getSum(const int a, const int b){
  119.     return d_s[b+1] - d_s[a];
  120.   }
  121. }
  122. ;
  123. #define main dummy_main
  124. int main(){
  125.   return 0;
  126. }
  127. #undef main
  128. class Solution{
  129.   public:
  130.   int maxRepOpt1(string S){
  131.     Grid1d<int> g;
  132.     int N, cnt[26]={}, i, j, k, res=0;
  133.     N = S.size();
  134.     for(i=0;i<(N);i++){
  135.       S[i] -= 'a';
  136.     }
  137.     for(i=0;i<(N);i++){
  138.       cnt[S[i]]++;
  139.     }
  140.     g.malloc(N);
  141.     for(i=0;i<(N);i++){
  142.       g[i] = S[i];
  143.     }
  144.     g.setDir();
  145.     for(i=0;i<(N);i++){
  146.       j = i - g.dw[i];
  147.       k = g.dw[i];
  148.       if(j>=0){
  149.         k++;
  150.         j--;
  151.         if(j>=0 && g[i]==g[j]){
  152.           k += g.dw[j];
  153.         }
  154.       }
  155.       chmax(res, min_L(k, cnt[g[i]]));
  156.       j = i + g.up[i];
  157.       k = g.up[i];
  158.       if(j<N){
  159.         k++;
  160.         j++;
  161.         if(j<N && g[i]==g[j]){
  162.           k += g.up[j];
  163.         }
  164.       }
  165.       chmax(res, min_L(k, cnt[g[i]]));
  166.     }
  167.     g.free();
  168.     return res;
  169.   }
  170. }
  171. ;
  172. // cLay varsion 20190818-1
  173.  
  174. // --- original code ---
  175. // #define main dummy_main
  176. // {}
  177. // #undef main
  178. // 
  179. // class Solution {
  180. // public:
  181. //   int maxRepOpt1(string S) {
  182. //     int i, j, k, N, res = 0;
  183. //     int cnt[26] = {};
  184. //     Grid1d<int> g;
  185. // 
  186. //     N = S.size();
  187. //     rep(i,N) S[i] -= 'a';
  188. //     rep(i,N) cnt[S[i]]++;
  189. // 
  190. //     g.malloc(N);
  191. //     rep(i,N) g[i] = S[i];
  192. //     g.setDir();
  193. // 
  194. //     rep(i,N){
  195. //       j = i - g.dw[i];
  196. //       k = g.dw[i];
  197. //       if(j>=0){
  198. //         k++;
  199. //         j--;
  200. //         if(j>=0 && g[i]==g[j]) k += g.dw[j];
  201. //       }
  202. //       res >?= min(k, cnt[g[i]]);
  203. // 
  204. //       j = i + g.up[i];
  205. //       k = g.up[i];
  206. //       if(j<N){
  207. //         k++;
  208. //         j++;
  209. //         if(j<N && g[i]==g[j]) k += g.up[j];
  210. //       }
  211. //       res >?= min(k, cnt[g[i]]);
  212. //     }
  213. // 
  214. //     g.free();
  215. //     return res;
  216. //   }
  217. // };
  218.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/ai8OrD
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!