Блог пользователя Furcifer

Автор Furcifer, история, 8 лет назад, По-английски

LightOJ 1189 Sum of Factorail

Problem Statement : Given an integer n, you have to find whether it can be expressed as summation of factorials. For given n, you have to report a solution such that

n = x1! + x2! + ... + xn! (xi < xj for all i < j) Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1018). Output

For each case, print the case number and the solution in summation of factorial form. If there is no solution then print 'impossible'. There can be multiple solutions, any valid one will do. See the samples for exact formatting.

MEMORY LIMIT : 32 MB

My Code :


using namespace std; ll fact[25]; map<ll,int>there; bool Check_ON(int mask,int pos) //Check if pos th bit (from right) of mask is ON { if( (mask & (1<<pos) ) == 0 )return false; return true; } void init() { fact[0] = 1; loop(i,1,19) fact[i] = fact[i-1]*i; int maxMASK = (1<<20) - 1; loop(mask,0,maxMASK) { int curmask = mask; ll curN = 0; loop(bitpos,0,20-1) { if(Check_ON(curmask,bitpos)) { curN+= fact[bitpos]; } } there[curN] = mask; } } int main() { init(); //cout<<there.size()<<endl; int tc,cas = 0; //write(); sfi(tc); while(tc--) { map<ll,int>::iterator it; ll N; sfl(N); CASE(cas); it = there.find(N); if(it==there.end()) { pf("impossible\n"); } else { int mask = there[N]; int flag = 0; loop(bitpos,0,20-1) { if(Check_ON(mask,bitpos)) { if(flag) pf("+%d!",bitpos); else pf("%d!",bitpos); flag = 1; } } pf("\n"); } cout<<there.size()<<endl; } return 0; }

The size of "there" is only 655360 . How did it consume 32 MB ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What happens when you run the program locally? How much memory does it consume?

I'd say that "map" is not very effective in terms of space usage. On my system one node of map takes 48 bytes if I store long long and int there. Add the fact that map allocates memory in heap and it may work imperfectly by allocating memory sparsely, and you easily exceed 32 MB.