Блог пользователя Agniva_

Автор Agniva_, история, 8 месяцев назад, По-английски

Problem Link 254383531

void solve(){
   int n; cin>>n;
   vi v(n); rep(i,0,n) cin>>v[i];
   int flag=1;
   rep(i,0,n/2){
     if(v[i]!=v[n-1-i]) {
        flag=0; break;
     }
   } 
   if(flag){
    yes
    return;
   }
   string s="";
   for(int i=0;i<n;i++) 
     if(v[i]!=v[0]) s=s+to_string(v[i]);
    string s2=s;
    reverse(s2.begin(),s2.end());
    if(s==s2) 
    {
        yes return;
    }
    s="";
    for(int i=0;i<n;i++) 
     if(v[i]!=v[n-1]) s=s+to_string(v[i]);
    s2=s;
    reverse(s2.begin(),s2.end());
    if(s==s2) 
    {
        yes return;
    }
    no 
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

because of s=s+to_string(), instread of this , you can use s+=to_string().

Spoiler
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

try to avoid using strings, this problem can be solved easily without really maintaining any additional $$$O(n)$$$ structure, in your for loop you are reversing a string which could grow linearly, so your code is essentially $$$O(n^2)$$$

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am not reversing the string inside the loop though but yeah i get your point-will avoid string operations

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      okay, I didnt see it, but still '+=' operator can take as much as length of the new string time, look at cpp docs here