- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
if (tp==-1 || c==a[tp]-'a') tp++; else {
l[ts+1]=la; p[ts+1]=ts;
l[ts]=l[tv]; r[ts]=tp-1; p[ts]=p[tv]; t[ts][c]=ts+1; t[ts][a[tp]-'a']=tv;
l[tv]=tp; p[tv]=ts; t[p[ts]][a[l[ts]]-'a']=ts; ts+=2;
tv=s[p[ts-2]]; tp=l[ts-2];
while (tp<=r[ts-2]) { tv=t[tv][a[tp]-'a']; tp+=r[tv]-l[tv]+1;}
if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts;
tp=r[tv]-(tp-r[ts-2])+2; goto suff;
}
Follow us!
Здесь.
По опыту - при мало-мальски нормальном алгоритме (не брутфорс) прога никогда не упиралась в память или таймауты...
P.S. Хотя, возможно, из-за такого отношения к задротству мы дальше региональных туров и не покатались...
ололо
первая и последняя для меня олимпиада по информатике проводилась за уютными синими борманд турбо с++
Потом в физмате - те самые синеокие борманд-пасцаль, да борманд-хуй-поймешь-си-или-кресты. Олимпиады были пиздец унылые и проверялись левой пяткой преподов. Стимула как-то по-особому готовиться к ними не было никакого.
А вот когда в институте катались на ACM - там уже можно было юзать шестую (вроде бы) вижуалку со всеми вытекающими.
> последняя
А мне не хотелось отказываться от халявной командировки на пару дней. Так что катались частенько :) Заодно закупались всяким железом да cd-r, которые в нашем городке стоили дороже. Ну и трофеи от олимпиад остались на память - флешка, мышка, да годная клава.
но ещё лучше, когда тебя в ней не напрягают и не возлагают надежд
на ту областную "олимпиаду" по программированию мы поехали вообще без подготовки, т.к. нас никто не натаскивал от слова вообще
максимум догадывались про сортировку пузырьком
так что просто весело провели время (и заодно я посмотрел, в каком плачевном материальном состоянии находится областной технический вуз)
Да никто особых надежд на нас и не возлагал... Все прекрасно понимали, что если кто-то прошел на региональный тур, поехал туда и занял не последнее место - это уже круто.
> напрягают
А из натаскиваний было только прорешивание задачек за неделю до олимпиады. Выбирали что поинтересней, да решали... А чтобы дротить каждый день без перерывов - такого у нас не было.
Прочитать как "дотить каждый день". Задумался.
P.S. Первая дота, емнип, уже была, но не зацепила.
>Не, мы тогда рубились в контру/старкрафт в машзалах
Нам нигде и никогда такого не позволяли. Разве что в школе пару уроков кваки было. А, и в универе на древних компах практика дюка нюкема, тоже один или джва раза.
Зато в универе те кто сумели разлочить, сидели на лентах в инете. С тогдашним дефицитом траффика, это было самое ценное времяпровождение.
тем временем инет был в основном только в терминальном доступе к линуксячему серверу
сидели в инете, читали новости и проверяли почту через links
зато в школьные годы я как раз ходил в 10-11 классе на курсы информатики, если быстро выполняешь план занятия, можно было бы поиграть в need for speed 4 на минимальной графе, или с товарищем в фифу-98
был отличный стимул сделать за 20 минут то, что рассчитано на час, и потратить оставшееся время на поиграть
тем более, что дома у меня не то что компа, даже сраной денди не было
nfs3,4 - божественные игры. И божественный саундтрек.
Просто этот зал был довольно мощным (в то время как будущие программисты писали лабы на дерьме с 98й виндой, в этом зале изучали ворд экономисты и менеджеры) и часто простаивал, а админил его наш хороший друг. Его начальник, входя в зал, ржал над тем, как некоторые запоздало пытаются свернуть контру и запустить борманд паскаль, после чего разгонял нас. А минут через 5 игра продолжалась...
P.S. Вспоминается, как мы just for lulz меняли заставку в главном меню контры на скриншот из BP.
P.P.S. А вот инет там был только платный (помимо школьного анлима, который дико лагал).
Ибо наивный поиск "aaa...b" в "aa...aa" длится вечность. KMP тут, наверное, помог бы.
Et tu, Bjarne?!
Даже в крестах, в 2011 не осилили тривиальный строковой алгоритм 70-х?
>KMP тут, наверное, помог бы.
А я предупреждал об возможности атак...
Сразу виден настоящий программист. Ленивый.
Пока поцоны пишут велосипеды, борманд берет либу, решает задачу в 10 раз быстрее и идёт читать ГК.
Мне кажется, у них может быть деформированное восприятие. Они вероятно, привыкли писать быстро, монолитно, не задумываясь о мелочах, в расчёте на положительный кейс.
А унылой реальности нужно писать так, чтобы код было максимально удобно читать и с рассчётом на то, что любая хрень может сломаться в любой момент.
Правда, это лишь измышления, напрямую с успешными олимпиадниками мне не вот прям работать приходилось. Видимо, они не опускаются до той работы, что достаётся мне.
В это время админ-программист только начинает рисовать диаграмму классов универсального решения этой и подобных проблем на 20 лет вперёд.
Думаю со временем каждый учится душить внутри себя подобные порывы и расставлять приоритеты.
"Хуяк-хуяк и в продакшен", имхо, тоже важное умение. Быстрое прототипирование, проверка идей, одноразовые скрипты и т.п. Самое сложное - заставить себя выкинуть этот прототип на помойку, а не обвешивать его деталями и проверками, превращая в ядро большой и сложной системы...
А потом понимаешь что вторая итерация не наступит никогда... никогда...
Если конечно кто нибудь не удалит код
олимпиадник тернарники не осилил?
В определённых кругах тернарники спорная штука.
max = a + (b-a)* (int)((a+b)/b==a)
x = (a + b) / 2
А поклонников старшего бита посылать за числами большей разрядности.
Убедитесь сами: http://gcc.godbolt.org/
P.S. Проверил, шланг заменяет на cmov, а питух-гцц оставляет умножение.
А зачем тогда в коде заменять ветвление на умножение?
ИМХО, красивее.
А так?
l[N], r[N] → lr[2][N]
p[N], s[N] → ps[2][N]
tv, ts → x[2]
И так далее.
В более общем случае кто-то будет городить свищи и горы тернарников, а кто-то напишет ассоциативный массив.
Хотя думаю оно сумеет в cmov...
Не хотелось бы гадать, ибо пути компилятора неисповедимы.