- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
typedef struct
{
int32_t x;
int32_t y;
} coord;
coord stack[1000000] = {{0,0}};
size_t stack_end = 1;
int checkstack(coord in)
{
for(size_t i = 0; i < stack_end; i++)
{
if((stack[i].x == in.x) && (stack[i].y == in.y))
{
return 0;
}
}
stack[stack_end] = in;
stack_end += 1;
return 1;
}
void consume_char(char ch, coord *c, uint32_t *sum)
{
switch( ch )
{
case '>':
c->x += 1;
break;
case '<':
c->x -= 1;
break;
case '^':
c->y += 1;
break;
case 'v':
c->y -= 1;
break;
default:
printf("ERROR!!");
exit(-1);
}
*sum += checkstack(*c);
}
const char *arr = "^><^>>>^<^v<v^^vv^><<^.....";
int main(void)
{
const char *arr_ptr = arr;
coord crd = {0,0};
uint32_t sum = 1;
while (*arr_ptr != '\0')
{
//printf("test\n");
consume_char(*arr_ptr, &crd, &sum);
arr_ptr++;
}
printf("%" PRIu32 "\n", sum);
return EXIT_SUCCESS;
}
Follow us!
А вот например решение от какого-то крестушка. Классы-хуяссы какие-то, нахуй это вообще нужно-то? Да и вся хрень в std::set решается, это вообще тупо. Я то хоть стек написал для запоминания хуйни. А всё прочее - какой-то тупой крестобойлерплейт
> using namespace std;
Это не крестух, это петух проткнутый!
А вот тут прямо баги полезли. set использует < чтобы сравнивать эквивалентность. Если a < b == false и b < a == false, значит a и b эквивалентны и b вставлять в сет не надо. Если бы он не использовал <=, то это бы отбрасывало дома с одинаковым х, но разным y. Теперь не отбрасывает, но повторяющиеся дома будет считать разными (наверное, технически запихивать в set что-то не подчиняющееся strict weak ordering — UB).
O(n) по памяти, O(N*log(N)) по времени.
З.Ы. Или даже хешмапку.
Я на Си тупо через стек хуйнул, мне было лень какой-то set писать.
Хотя на их размерах ввода О(N²) у стека вообще не проблема, не удивлюсь, если из-за накладных расходов на хешмапу она будет медленнее.
Так то на тыще уже будет миллион чтений против десяти тысяч (мапа) или тысячи (хешмапа)...
Это надо прям сильно выдрочить стек и написать совсем анскилльную хешмапу, чтобы проиграть.
У *мап же значения в динамически аллоцируемых нодах хранятся, цена аллокаций может быть слишком велика.
У unordered с этим вроде получше, там массивы, а у тех, что деревьями реализуются — по аллокации на каждое значение.
Хрен знает, бенчить надо.
Потом это толи в С++14, толи в 17 пофиксили.
qsort то можно на сишке юзать?
Даже если нет, сортировку легче нахуячить с нуля, чем дерево/хешмапу.
Более эффективная работа если по одним и тем же местам бегают?