Hm, I thought that programming contests are about algorithms and not performance tunning. Finally I found “useful improvements”.
1.) multidimensional array -> one dimensional
I always thought that when I have multidimensional array (in following example 3D):
and I want to get value for
int v = a[i][j][k];
C/C++ calculates memory position like
int v = a + i * B * C * sizeof(int) + j * C * sizeof(int) + k;
In this problem I found, that when you perform such calculation in code, performance is 4-times better on my computer (shame on you C/C++).
2.) Loop unwinding (wikipedia)
Applying first improvement was not enought, still getting TLE. When I changed state update from
for ( int j = 0; j < MODSL; ++j )
s->mods[j] = (act->mods[j] * 10 + v) % MODS[j];
s->mods = s->mods == 0 ? 0 : 1;
s->mods = (10 * act->mods + v) % 3;
s->mods = (10 * act->mods + v) % 4;
s->mods = v == 5 ? 0 : 1;
s->mods = (10 * act->mods + v) % 7;
performance improved slightly, but it was finally enough to pass time limit.