Как хранить построенный бор в памяти максимально сжато?
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 КБ.