you print Ask Shiftman for help. once again, although the correct answer is Perfect

Я получил такой вердикт, выводя "Ask Shiftman for help." как только встречалось в цикле подходящее условие, вместо того чтобы проверить все отрезки до конца на наличие случая "Let's search for another office."

Do not forget case for "Ask Shiftman for help"

http://s020.radikal.ru/i702/1410/52/a428d102a994.jpg

Why?



Edited by author 11.10.2014 19:51

getting WA 39, can anyone please provide some test cases?

My program gets wa#3
test 3:
6
1 2 3 4 5 6
1 1
1 6
2 3
3 3
4 4
5 5
my program out:
Perfect!
1 3 4 5 6 2

it's wrong?

For solving this problem I used advanced bipartite graph theory. But it work slowly(about 0.6sec). Very interesting how solve more quickly. Please, give me some hints.(My e-mail: scarlet.flower@list.ru)

5
1 2 3 4 5
1 3
1 3
4 5
4 5
4 5

I think the correct answer of this sample is "Let's search for another office.", but my program outputs "Ask Shiftman for help."

WA #39
Did somebody have the same problem?

Edited by author 24.03.2012 14:17

Edited by author 24.03.2012 14:17

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