ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1654. Шифровка

Tle in 6? Look at source code.
Послано Cebiyev_Ferhad_Qafqaz U. 28 окт 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.
Послано JAVATAR 16 апр 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.
Послано Bogatyr 4 окт 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.
Послано roman velichkin 12 июл 2019 20:08
This helped me, thanks.