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

Обсуждение задачи 1915. Руины титанов: воссоздание былого

@admin I think #42 is illegal.
Послано William Chou 6 май 2013 20:56
The problem say that "It is guaranteed that during the experiment each time a coin was to be removed the stack was not empty."
But when I submit such a brute force code:
--------------------
        if (x > 0) a[t++] = x;
        else if (x == 0) {
            if (t + t < maxn) {
                copy(a, a + t, a + t);
                t += t;
            }
        }
        else printf("%d\n", a[--t]);
--------------------
It crashed at #42. Then, I modified the last "else branch" into:
--------------------
        else if (t) printf("%d\n", a[--t]);
--------------------
I got WA at #42.
Re: @admin I think #42 is illegal.
Послано Erop [USU] 8 май 2013 00:55
What if t = maxn/2 + 1 and than t + 1 pop operations?
For example:
1000000
1
0
0
..
0 (20 times)
-1
-1
..
-1 (1000000 - 21 times)

You will store only 2^19 copies in array, and get crash
Re: @admin I think #42 is illegal.
Послано William Chou 10 май 2013 18:41
Oh..Sorry..It's my fault.
I only set the size of a to 1000001 * 2, but I forgot to modify the maxn....
I apologize for asking so stupid question.T_T
Accepted now, thank you very much.
Re: @admin I think #42 is illegal.
Послано kaa..........ai 27 июл 2013 11:07
Yeah,I've made the same mistake,and thank you so much!