Как хранить построенный бор в памяти максимально сжато?
MLE#7 на задаче http://acm.timus.ru/problem.aspx?space=1&num=1269.
Текущая структурка:
struct Vertex
{
list<pair<char, int> > next;
int link, prev, near;
char prevc;
}v[100500];
Бор на словаре из не слов суммарной длинны не более 100000. Надо вжать в 8мб.
Как это сделать? =)
У нас сдано так:
char tmp[2000000];
struct Dyn{
int Cnt;
int Nxt;
};
#define MAX 2000000
//Bour
char tChar[MAX];
int tNbr[MAX];
int tLng[MAX];
Может показаться, что это не пройдёт по памяти, но тут массивы используются не полностью. Тимус оценил занятость памяти в 2 312 КБ.
I know its late, however, I had the same problem. I tried different approaches, the best I got was using a global hash table, but this got me MLE at test 10. Did you manage to solve the problem ? If so, what was your approach ?
I have used one global hash table too, my solution uses only 4 MB of memory.
еще вроде бы можно на одной большой хэш таблице все делать ;)
Свежая идея!