LightOj 1189 - Sum of Factorials

// Accepted

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>

#define sf scanf
#define pf printf

using namespace std;

typedef long long LL;
typedef map<LL, bool> mpbll;

LL f[22];

void factorial()
{
    int i;

    f[0] = 1;
    f[1] = 1;

    for(i=2; i<21; i++)
    {
        f[i] = f[i-1] * i;
    }

    //for(i=1; i<21; i++) cout << f[i] << " ";
}

int Search_Binary(LL itm)
{
    int lo=1, hi=20, mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(f[mid] == itm)
        {
            return mid;
        }

        else if(f[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(f[mid] < itm)
        {
            lo = mid + 1;
        }
    }

    return lo;
}

int ans[21] , ar[22];

int main()
{
    factorial();
    LL n , tmp;
    mpbll mp;
    int t , tc=0;
    sf("%d", &t);

    while(t--)
    {
        mp.clear();

        int len=0 , r = -1;

        sf("%lld", &n);

        tmp = n;

        bool impossible = true;

        pf("Case %d: ", ++tc);

        while(n)
        {
            r = Search_Binary(n);

            if(f[r] == n)
            {
                r=r;
            }

            else
            {
                r--;
            }

            if(!mp[r])
            {
                n -= f[r];
                ans[len++] = r;
                mp[r] = true;
            }

            else
            {
                break;
            }
        }

        /* origin */ //for(int i=0; i<len; i++) cout << ans[i] << " "; return 0;

        LL sum=0;
        int arlen=0;

        for(int i=0; i<len; i++)
        {
            sum += f[ans[i]];
            ar[arlen++] = ans[i];

            if(sum == tmp)
            {
                impossible = false;
                break;
            }
        }

        if(sum + f[0] + f[1] == tmp)
        {
            ar[arlen++] = 1;
            ar[arlen++] = 0;
            impossible = false;
        }

        //for(int i=0; i<arlen; i++) cout << ar[i] << " ";

        if(impossible)
        {
            pf("impossible");
        }

        else
        {
            bool fl=false;

            for(int i=arlen-1; i>=0; i--)
            {
                if(!fl)
                {
                    pf("%d!",ar[i]);
                    fl=true;
                }

                else
                {
                    pf("+%d!",ar[i]);
                }
            }
        }

        pf("\n");
    }

    return 0;
}