Advertisement
ismaeil

B. Baby name

Aug 30th, 2020
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 5e2;
  5. string f ,m;
  6. int F ,M;
  7.  
  8. string Read(){
  9.     static char Buff[N];
  10.     scanf("\n%s" ,Buff);
  11.     return Buff;
  12. }
  13.  
  14. string GetMax(string &s ,int n) {
  15.     char mx = s[0];
  16.     for(int i = 1 ; i < n ; i++)
  17.         mx = max(mx ,s[i]);
  18.  
  19.     vector< int > idx;
  20.     for(int i = 0 ; i < n ; i++)
  21.         if( s[i] == mx ) idx.push_back(i);
  22.  
  23.     char lastResChar = (char)0;
  24.     vector< bool > vis(n ,false);
  25.     int Size = 0 ,resIdx = idx[0];
  26.     for(int i = idx[0] ; i < n ; i++){
  27.         if( i == n - 1 || s[i] != mx ){
  28.             lastResChar = s[i];
  29.             vis[i] = true;
  30.             Size += 1;
  31.             break;
  32.         } else {
  33.             vis[i] = true;
  34.             Size += 1;
  35.         }
  36.     }
  37.  
  38.     for(auto id : idx) if( !vis[id] ) {
  39.         int Sz = 0;
  40.         char lastTmpChar = (char)0;
  41.         for(int i = id ; i < n ; i++){
  42.             if( i == n - 1 || s[i] != mx ){
  43.                 lastTmpChar = s[i];
  44.                 vis[i] = true;
  45.                 Sz += 1;
  46.                 break;
  47.             } else {
  48.                 vis[i] = true;
  49.                 Sz += 1;
  50.             }
  51.         }
  52.  
  53.         if( ( Sz > Size ) || ( Sz == Size && lastResChar < lastTmpChar ) ){
  54.             resIdx = id;
  55.             Size   = Sz;
  56.         }
  57.     }
  58.  
  59.     string Res;
  60.     for(int i = resIdx ; i < n ; i++)
  61.         Res += s[i];
  62.  
  63.     return Res;
  64. }
  65.  
  66. int main() {
  67.     f = Read(); F = f.size();
  68.     m = Read(); M = m.size();
  69.  
  70.     string mxF = GetMax(f ,F);
  71.     string mxM = GetMax(m ,M);
  72.  
  73.     F = mxF.size();
  74.     string BabyName(1 ,mxF[0]);
  75.  
  76.     for(int i = 1 ; i < F ; i++){
  77.         if( mxF[i] >= mxM[0] ) {
  78.             BabyName += mxF[i];
  79.         } else break;
  80.     }
  81.  
  82.     BabyName += mxM;
  83.     for(char c : BabyName) printf("%c" ,c);
  84.     return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement