ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1872. Spacious Office

TL #16
Posted by marqueewinq 16 Nov 2011 20:41
Hi there.
I've got TL on 16-th with exceedence of 42 ms. Would anybody be so kind to help me manage with it?

In my solution, i am building n lists: in i-th list, there are indexes of teams, that can occupy i-th office. After that, i'm running through all n lists, trying to find any OK variant.

{{{
void run(int deep)
{
    if (deep == n)
    {
        if (final.size() == 0)
            final = answer;
        else
        {
            cout << cAnswerIsNotUnique << "\n";
            exit(0);
        }
    }
    else
    {
        for (int i = 0; i < ok[deep].size(); i++)
        {
            int target = ok[deep][i];
            if (!cap[target])
            {
                cap[target] = true;
                answer[target] = deep;

                run(deep + 1);
                // cleanup
                answer[target] = -1;
                cap[target] = false;
            }
        }
    }
}
}}}

How can i modify my algorithm for better runtime?
I would be glad for any clue.
Thx.

Edited by author 16.11.2011 20:45