|
|
I was getting wa6 because the salary[0] not equal to 0 5 4 2 1 1 3 2 1 4 3 1 4 0 1 Impossible after 4 statements I have wa in 7 test Check this test 4 3 1 2 100 3 0 100 1 3 -100 Impossible after 3 statements Edited by author 04.04.2009 22:09 But I think the answer should be "Impossible after 1 statements"...I used BFS and I also got WA on test 7 afte statement 1 it will be: 0 100 0 problem?!?!? Edited by author 17.05.2014 22:59 before AC my prog failed on these tests: 1) 7 3 2 1 1000000000 3 1 15 4 5 -20 answer: Possible 0 0 1000000000 15 0 20 0 2) 7 4 2 1 1000000000 3 1 15 4 5 -20 4 2 1 answer: Impossible after 4 statements 3) 8 4 1 2 200 2 3 999999800 3 1 -1000000000 4 0 5 answer: Possible 0 1000000000 999999800 0 5 0 0 0 Test 2 is not correct due to statement restrictions. have no ideas. i've runned my random test generator and my program passed over 1000 tests, but wa. help, please. This hand-made test helped me with WA#16: 5 3 1 2 -2 4 3 2 4 2 -1 The possible answer is: Possible 0 1 3 0 2 Good luck. Глащенко Никита, thank you very much! Really useful test! Hello all. I am doing task #1701, but ,actually, my question is also related to other equal tasks: how can you not exceed the time limit when the task supposes large array as the answer? For instance, in mentioned task the time is limited to 2 seconds. In case when N == 50 000, if possible set of emplyee's salaries exists, you need write 50 000 strings to console. But, as i have found out by measurig, only outputting array to the console takes over 3-5 seconds. Test it using C# and C++ with array of int values set to "0". Edited by author 05.03.2018 09:04 "It is known that no workman gets more than 10^9 rubles." Can't anyone of them gets more than 10^9 or it's only guarantee of existense solution with no more 10^9? If solution with no more than 10^9 rubles, output it. Else find the first record, after which salary with more than 10^9 rubles appears (or contradiction between salaries). I use binary search to find the answer. My algo to check answer: 1) Sort every edge by first man (we get two edges from every record) 2) Use dfs to find dependend groups. 3) First, make all salaries 0. 4) Get mens' salaries by going one by one in array of edges. Here we can find a contradiction between salaries. 5) In Vasiliy's group check all salaries on <0 or >10^9. 6) In other group find the minimum and the maximum salaries and if max-min>10^9 then it's wrong record. Else every salary=salary-min to make all salaries in [0..10^9]. It seems correct, but my program in Java get WA 8 and ONE Pascal program get WA 1, WA 8 and WA 16 O_o How do you search the answer? Separately for every dependent group? And what is the answer (you get salaries in 4 point so answer isn't salaries)? Answer is the number of last possible record. If Answer<m I output "Impossible ..." else I write the mens' salaries. No. I form every dependent group every time in binary search, becouse some record are unavailable for this. I form dependent group only for check answer. Thank you for your help becouse I have no idea... Algorithm seems to be correct. I think mistake in program. Thank you very much. I will try to find a mistake. I found error. I must sort edges by bfs, not simple sort. Edited by author 16.01.2011 13:22 Please, give some useful tests. Input: 5 1 1 2 1 Output: Possible 0 1 0 0 0 Just use an array of link and some small skills can pass it! O(nlog2n) [code deleted] Edited by moderator 06.10.2011 16:00 Don't think it is correct to post AC code or even another pieces of code anyway! BTW, I solved this problem using binary search by the answer + DFS, without any data structure at all. Please help. You could not will lay out an approximate kind 8 tests. Edited by author 12.05.2010 03:28 Try tests: Input 3 1 1 2 100 Output 0 100 0 Input 3 1 1 2 -100 Output 0 0 100 Edited by author 21.06.2011 11:44 I submited one file for 3 times and got 3 different results: WA 1, WA 8 and WA 16... Sorry. I think it's my fail. $R+ and $Q+ helped me to get only WA8 No, WA1 with same text again... PS Sorry for spam... Edited by author 15.01.2011 17:34 Edited by author 15.01.2011 17:43 All posted tests work well... Ha-ha... 6 5 1 0 1 3 2 1 5 4 1 2 1 0 4 1 0 answer: Possible 0 1 1 2 1 2 Why the input of 3 2 1 0 871 1 2 903 Answer is "Impossible after 2 statements"? I think it is possible We can guess: 0: 100 1: 971 2: 68 it's impossible because value of Vassily's wage always equals 0. 0: 0 1: 871 2: -32 (WRONG) I see! Thank you very much! thank you very much Alex !!! guys, could you help me? my c# solution crashes without additional details on 2nd test. does anyone have an idea what this test is about or some hints. Thanks in advance. give me some test 8 please!!! I spent about 20 attempts on this problem (yea, it's funny). It's all because i got wa12 instead of crash 12 when my recursive dfs led to stack overflow. P.S. Test 12: n=50000,m=49999, and [probably] graph is line. Edited by author 06.04.2009 19:04 |
|
|