|
|
Я получил такой вердикт, выводя "Ask Shiftman for help." как только встречалось в цикле подходящее условие, вместо того чтобы проверить все отрезки до конца на наличие случая "Let's search for another office." Do not forget case for "Ask Shiftman for help" 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? answer: 1 6 2 3 4 5 Edited by author 25.02.2018 18:18 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) Maximum matchings in bipartite graph is almost enough to solve it + some "magic" :) Maybe maximum flow algos' works better here... My complexity was O(V*E), 0.3sec Just gredy. Also, O(NlogN) solution exists 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." I just couldn't squeeze my bipartite matching through the TL... Anyway, a nice test against extra greediness: 3 40 50 60 30 70 20 40 50 50 Perfect! 3 1 2 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 |
|
|