Завтра в 18:00 по Москве состоится первый из интернет-туров COCI - хорватской олимпиады по программированию. Как обычно - шесть задач на три часа. Система - как на старых IOI (без фидбека, каждый тест оценивается в отдельности). Никакой мегасложной регистрации не надо - всего лишь регистрируемся в тестирующей системе и логинимся в COCI Contest #1.
От себя: мне нравятся такие туры. Очень вкусные задачки вкупе с кошерной системой оценки :-)
Спасибо yeputons за незаметно поданную идею запостить про COCI на КФ.
А дополнительно регистрироваться нужно(я имею ввиду на соревнование), и если нужно то как?
Также как и, например, сегодня на acm.timus.ru, да?
В общем, если вам удалось залогиниться в тестирующую систему, не волнуйтесь. Ничего важного вы не пропустите.
вопрос снят
Вопрос снят, я понял условие
for (int i = 0; i < n; i++)
{
one[i] = (a[i] >> 1) | (a[i] << 1);
two[i] = (a[i] >> 2) | (a[i] << 2);
}
for (int i = 0; i < n; i++)
{
b[i].reset();
if (1 < i) b[i] |= one[i - 2];
if (0 < i) b[i] |= two[i - 1];
if (i < n - 1) b[i] |= two[i + 1];
if (i < n - 2) b[i] |= one[i + 2];
}
Потом можно заметить что клетки у которых 1 или 2 и она такого же цвета как начально, то она всегда будет доступна, поэтому мы делаем маску поля по таком критерию и
for (int i = 0; i < n; i++)
a[i] = b[i] & mask[i];
Все остальные значение рассматриваем отдельно, храня все клетки которые доступны в текущий момент времени.
int add(int t, int i)
{
if (t > T) return 0;
next[i] = last[t];
last[t] = i;
return 0;
}
...
for (int i = last[t], j; i; i = j)
{
a[x[i]].set(y[i], b[x[i]].test(y[i]));
j = next[i];
add(t + d[i], i);
}
В конце успел только запустить макстест (30 100000 и все 3), около 6 секунд отработало. Думаю если ещё сделать маски для каждого 3 поле, 4 и так пока будет улучшаться, то должно зайти...
const int MAXT = 1000001;
const int MAXK = MAXN * MAXN;
bitset <MAXN> a[MAXN], b[MAXN];
bitset <MAXN> mask[MAXN];
bitset <MAXN> one[MAXN], two[MAXN];
int x[MAXK], y[MAXK], d[MAXK];
int next[MAXK];
int last[MAXT];
Очень мало, а поля можно для первой сотни сделать, думаю хватит.
Такая оптимизация ускоряет с 6 до за 2.3 сек, за счет того что все 3 мы будет обрабатывать каждый третий ход все сразу, а не каждую по отдельности...
Хм. Что-то мне подсказывает, что неправда, что почти все большие позиции, где открыты только единички, имеют одинаковые ответы. Хотя бы из-за чётности ходов коня (в шахматной раскраске доски)
UPD: Хотя тут подсказывают, что все большие числа нечётны. Не могу не согласиться с этим :-)
Тем самым, делаем нужное количество ревёрсов на первом шагу ручками, а далее считаем количество инверсий.
А потом прибавляем к ответу количество инверсий.
Доказывается так: после первого шага максимальная длина реверса будет два. Значит, их будет ровно столько, сколько инверсий.
А тест 5 4 1 3 5 2?
Ответ 5, а должно быть 3.
"slopes all hav even length when partitioned for the first time"
Плес, кажется, можно жадно...Рассмотрим два множества: 1) девушки с - и парни с + и 2) девушки с + и парни с минусом. Народ из разных групп не может создать пару...Далее, в каждой группе жадно набираем пары
UPD Это действительно работает (110 таки)
Там разбивается на две подзадачи (мальчики, которые хотят девочек повыше и девочки, которые хотят мальчиков пониже и наоборот).
А дальше замечается, что каждая задача решается жадно посортили и тех, и других по росту и перебрали ответ. Проверку тоже надо соптимизировать.
Понятно, что люди из разных групп друг с другом танцевать не будут. Значит решаем задачу внутри каждой из групп. Ну а внутри, например, первой группы задача вообще глупая - жадно идём с самого низенького мальчика, подбирая ему самую низкую девочку. Аналогично для второй группы.
Означает ли столь конкретный вопрос то, что ты решил sort(про сортировку)??)
Если кто придумал как решать последние две, можете сразу написать идею и больше не ждать просьб;)
Тупо, что нельзя увидеть таблицу результатов. У меня 398 баллов (0 за Sort, 48 за Skakac).
Ну что, сколько у кого по Skakac?
У меня 64 :-(
У меня какие-то позорные WA на 2, 4, 5 и 9 тесте. Хочу тесты.
Task: Skakac
На кф мои 6 секунд превращаются в "Использовано: 1280 мс, 5280 КБ"
UPD. Оптимизированное, которое работало 2 секунды переходит в "Использовано: 730 мс, 5284 КБ".
Например, в задаче xor у них в конце тестов мусор.
Любая единичка в i-ом разряде даёт вклад в ответ 2i. Соответственно, считаем по каждому разряду количество единичек в этом разряде, количество нулей, перемножаем их и домножаем на 2i. И прибавляем к ответу.
http://pastebin.com/0s5bJwkW.
Прошел только первый тест, но идея такая же. Подскажите, пожалуйста, где у меня ошибка. Спасибо.
там перепроверку сделали ;)
Кто-нибудь может мне объяснить почему брут на задачу xor :
Возможно, ans получается очень большим.
инт64 забыли.
Правда, по словам Егора, у них в конце тестов мусор, из-за которого у него кушающее мультитест решение тоже ломается. Может тут тоже какая-то гадость сыграла свою роль.
Пишу так же, как указывали здесь в комментариях, но ни один тест у них не проходит.