fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void*wmem;
  5. char memarr[96000000];
  6. struct Rand{
  7.   unsigned x;
  8.   unsigned y;
  9.   unsigned z;
  10.   unsigned w;
  11.   Rand(void){
  12.     x=123456789;
  13.     y=362436069;
  14.     z=521288629;
  15.     w=(unsigned)time(NULL);
  16.   }
  17.   Rand(unsigned seed){
  18.     x=123456789;
  19.     y=362436069;
  20.     z=521288629;
  21.     w=seed;
  22.   }
  23.   inline unsigned get(void){
  24.     unsigned t;
  25.     t = (x^(x<<11));
  26.     x=y;
  27.     y=z;
  28.     z=w;
  29.     w = (w^(w>>19))^(t^(t>>8));
  30.     return w;
  31.   }
  32.   inline double getUni(void){
  33.     return get()/4294967296.0;
  34.   }
  35.   inline int get(int a){
  36.     return (int)(a*getUni());
  37.   }
  38.   inline int get(int a, int b){
  39.     return a+(int)((b-a+1)*getUni());
  40.   }
  41.   inline long long get(long long a){
  42.     return(long long)(a*getUni());
  43.   }
  44.   inline long long get(long long a, long long b){
  45.     return a+(long long)((b-a+1)*getUni());
  46.   }
  47.   inline double get(double a, double b){
  48.     return a+(b-a)*getUni();
  49.   }
  50.   inline int getExp(int a){
  51.     return(int)(exp(getUni()*log(a+1.0))-1.0);
  52.   }
  53.   inline int getExp(int a, int b){
  54.     return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  55.   }
  56. }
  57. ;
  58. inline int my_getchar_unlocked(){
  59.   static char buf[1048576];
  60.   static int s = 1048576;
  61.   static int e = 1048576;
  62.   if(s == e && e == 1048576){
  63.     e = fread_unlocked(buf, 1, 1048576, stdin);
  64.     s = 0;
  65.   }
  66.   if(s == e){
  67.     return EOF;
  68.   }
  69.   return buf[s++];
  70. }
  71. inline void rd(int &x){
  72.   int k;
  73.   int m=0;
  74.   x=0;
  75.   for(;;){
  76.     k = my_getchar_unlocked();
  77.     if(k=='-'){
  78.       m=1;
  79.       break;
  80.     }
  81.     if('0'<=k&&k<='9'){
  82.       x=k-'0';
  83.       break;
  84.     }
  85.   }
  86.   for(;;){
  87.     k = my_getchar_unlocked();
  88.     if(k<'0'||k>'9'){
  89.       break;
  90.     }
  91.     x=x*10+k-'0';
  92.   }
  93.   if(m){
  94.     x=-x;
  95.   }
  96. }
  97. inline int rd(char c[]){
  98.   int i;
  99.   int sz = 0;
  100.   for(;;){
  101.     i = my_getchar_unlocked();
  102.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  103.       break;
  104.     }
  105.   }
  106.   c[sz++] = i;
  107.   for(;;){
  108.     i = my_getchar_unlocked();
  109.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  110.       break;
  111.     }
  112.     c[sz++] = i;
  113.   }
  114.   c[sz]='\0';
  115.   return sz;
  116. }
  117. inline void rd(string &x){
  118.   char*buf = (char *)wmem;
  119.   rd(buf);
  120.   x = buf;
  121. }
  122. struct MY_WRITER{
  123.   char buf[1048576];
  124.   int s;
  125.   int e;
  126.   MY_WRITER(){
  127.     s = 0;
  128.     e = 1048576;
  129.   }
  130.   ~MY_WRITER(){
  131.     if(s){
  132.       fwrite_unlocked(buf, 1, s, stdout);
  133.     }
  134.   }
  135. }
  136. ;
  137. MY_WRITER MY_WRITER_VAR;
  138. void my_putchar_unlocked(int a){
  139.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  140.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  141.     MY_WRITER_VAR.s = 0;
  142.   }
  143.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  144. }
  145. inline void wt_L(char a){
  146.   my_putchar_unlocked(a);
  147. }
  148. inline void wt_L(const char c[]){
  149.   int i=0;
  150.   for(i=0;c[i]!='\0';i++){
  151.     my_putchar_unlocked(c[i]);
  152.   }
  153. }
  154. inline void wt_L(string &x){
  155.   int i=0;
  156.   for(i=0;x[i]!='\0';i++){
  157.     my_putchar_unlocked(x[i]);
  158.   }
  159. }
  160. unsigned long long HashMap_ullP_L[4];
  161. template<class KEY, class VAL> struct HashMap{
  162.   char*used;
  163.   KEY*key;
  164.   VAL*val;
  165.   int mem;
  166.   int n;
  167.   int mask;
  168.   HashMap(){
  169.     mem = 0;
  170.   }
  171.   ~HashMap(){
  172.     free();
  173.   }
  174.   void expand(int nn){
  175.     if(mem >= nn){
  176.       return;
  177.     }
  178.     if(mem){
  179.       free();
  180.     }
  181.     mem = nn;
  182.     used = new char[nn];
  183.     key = new KEY[nn];
  184.     val = new VAL[nn];
  185.   }
  186.   void free(){
  187.     if(mem){
  188.       mem = 0;
  189.       delete[] used;
  190.       delete[] key;
  191.       delete[] val;
  192.     }
  193.   }
  194.   void init(int nn){
  195.     int i;
  196.     n = 1;
  197.     nn = nn + (nn + 1) / 2;
  198.     while(n < nn){
  199.       n *= 2;
  200.     }
  201.     mask = n - 1;
  202.     expand(n);
  203.     for(i=(0);i<(n);i++){
  204.       used[i] = 0;
  205.     }
  206.   }
  207.   inline int getHash(const int a){
  208.     unsigned long long d = a;
  209.     d = (((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) & mask;
  210.     return d;
  211.   }
  212.   inline int getHash(const unsigned a){
  213.     unsigned long long d = a;
  214.     d = (((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) & mask;
  215.     return d;
  216.   }
  217.   inline int getHash(const long long a){
  218.     unsigned long long d = a;
  219.     d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
  220.     return d;
  221.   }
  222.   inline int getHash(const unsigned long long a){
  223.     unsigned long long d = a;
  224.     d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
  225.     return d;
  226.   }
  227.   inline int getHash(const pair<int,int> a){
  228.     unsigned long long d = (((unsigned long long)a.first) << 32) + ((unsigned long long)a.second);
  229.     d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
  230.     return d;
  231.   }
  232.   inline VAL& operator[](const KEY a){
  233.     int k = getHash(a);
  234.     for(;;){
  235.       if(used[k]==1 && key[k]==a){
  236.         break;
  237.       }
  238.       if(used[k]==0){
  239.         used[k] = 1;
  240.         key[k] = a;
  241.         break;
  242.       }
  243.       k = (k+1) & mask;
  244.     }
  245.     return val[k];
  246.   }
  247.   inline bool exist(const KEY a){
  248.     int k = getHash(a);
  249.     for(;;){
  250.       if(used[k]==1 && key[k]==a){
  251.         return true;
  252.       }
  253.       if(used[k]==0){
  254.         break;
  255.       }
  256.       k = (k+1) & mask;
  257.     }
  258.     return false;
  259.   }
  260.   template<class S> inline bool exist(const KEY a, S &res){
  261.     int k = getHash(a);
  262.     for(;;){
  263.       if(used[k]==1 && key[k]==a){
  264.         res = val[k];
  265.         return true;
  266.       }
  267.       if(used[k]==0){
  268.         break;
  269.       }
  270.       k = (k+1) & mask;
  271.     }
  272.     return false;
  273.   }
  274. }
  275. ;
  276. int N;
  277. string S;
  278. string T;
  279. HashMap<int,int> hs;
  280. int solve(int dep, int len, int cur){
  281.   int i;
  282.   if(dep==len){
  283.     if(hs.exist(cur)){
  284.       return 0;
  285.     }
  286.     return 1;
  287.   }
  288.   for(i=(0);i<(26);i++){
  289.     T[dep] = 'a' + i;
  290.     if(solve(dep+1,len,cur*27+i)){
  291.       return 1;
  292.     }
  293.   }
  294.   return 0;
  295. }
  296. int main(){
  297.   wmem = memarr;
  298.   {
  299.     int i;
  300.     int j;
  301.     int k;
  302.     Rand rnd;
  303.     for(i=(0);i<(20);i++){
  304.       rnd.get(2);
  305.     }
  306.     for(i=(0);i<(4);i++){
  307.       for(j=(0);j<(32);j++){
  308.         k = rnd.get(1,62);
  309.         HashMap_ullP_L[i] |= (1ULL << k);
  310.       }
  311.       HashMap_ullP_L[i] |= (1ULL << 0);
  312.       HashMap_ullP_L[i] |= (1ULL << 63);
  313.     }
  314.   }
  315.   int len;
  316.   int i;
  317.   int j;
  318.   int k;
  319.   rd(N);
  320.   rd(S);
  321.   for(len=1;;len++){
  322.     int WYIGIcGE;
  323.     hs.init(N);
  324.     for(i=(len);i<(N+1);i++){
  325.       k = 0;
  326.       for(j=(0);j<(len);j++){
  327.         k = k * 27 + S[i-len+j] - 'a';
  328.       }
  329.       hs[k] = 1;
  330.     }
  331.     T = "";
  332.     for(WYIGIcGE=(0);WYIGIcGE<(len);WYIGIcGE++){
  333.       T += 'a';
  334.     }
  335.     if(solve(0, len, 0)){
  336.       break;
  337.     }
  338.   }
  339.   wt_L(T);
  340.   wt_L('\n');
  341.   return 0;
  342. }
  343. // cLay version 20201123-1
  344.  
  345. // --- original code ---
  346. // int N;
  347. // string S, T;
  348. // HashMap<int,int> hs;
  349. // 
  350. // int solve(int dep, int len, int cur){
  351. //   if(dep==len){
  352. //     if(hs.exist(cur)) return 0;
  353. //     return 1;
  354. //   }
  355. //   rep(i,26){
  356. //     T[dep] = 'a' + i;
  357. //     if(solve(dep+1,len,cur*27+i)) return 1;
  358. //   }
  359. //   return 0;
  360. // }
  361. // 
  362. // {
  363. //   int len, i, j, k;
  364. //   rd(N,S);
  365. //   for(len=1;;len++){
  366. //     hs.init(N);
  367. //     rep(i,len,N+1){
  368. //       k = 0;
  369. //       rep(j,len) k = k * 27 + S[i-len+j] - 'a';
  370. //       hs[k] = 1;
  371. //     }
  372. //     T = "";
  373. //     rep(len) T += 'a';
  374. //     if(solve(0, len, 0)) break;
  375. //   }
  376. //   wt(T);
  377. // }
  378.  
Time limit exceeded #stdin #stdout 5s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EVz38E
language:
C++ (gcc 8.3)
created:
3 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!