ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1654. Cipher Message

Tle in 6? Look at source code.
Posted by Cebiyev_Ferhad_Qafqaz U. 28 Oct 2010 22:49

#include <iostream>
#include <cstdlib>
#include <deque>

using namespace std;

int main()
{
    int h;
    char s[200001];
    scanf("%s", &s);
    int n=strlen(s);
    deque<char> v (s, s + n  );

    if(v.size()==2  && v[0]==v[1] ) return 0;
    b: h=2;
    for(int i=0; i<v.size()-1 ;i++)
          if(v[i] == v[i+1])
        {
            v.erase(v.begin() + i);
            v.erase(v.begin() + i);
            h=1;
        }

    if(h==1) goto b;

    for(int i=0; i<v.size(); i++)
        cout << v[i];

        return 0;
}
Re: Tle in 6? Look at source code.
Posted by JAVATAR 16 Apr 2012 01:57
Hello,

If you are still working on this, let you know that it can't be solved with erase.
I implemented a similar algorithm in Java which goes through the string and deletes the successful characters and it also got TLE on test 6.The easiest way is removing the successful characters as you read them.
nc->new character from the input.

if(i!=-1&&c[i]==nc){//new char is equal to the char at the end of the string, remove it
         i--;
     }else{ //add the new char to the string
         i++;
         c[i]=nc;
     }
Hope this helps
Re: Tle in 6? Look at source code.
Posted by Bogatyr 4 Oct 2012 04:10
You got TLE because deque has poor deletion performance on positions other than the front and back.
Re: Tle in 6? Look at source code.
Posted by roman velichkin 12 Jul 2019 20:08
This helped me, thanks.