|
|
If you have some troubles with passing 16th test, try 20 3 10 5 5 1 4 8 12 16 I've passed test 16, but stuck on 17... And, by the way, what is right answer on your test? If my solution is correct(it got AC),then it's 0 I'm can't pass test #22 :( This tests very helped me to pass test #16 and test #22: 7 3 5 2 1 1 answer 0 7 4 6 2 1 1 answer 0 Edited by author 09.03.2009 14:55 Could you explain please how to get answer 0 in your tests? like in 1st for example: worm is from 1 to 4 [1;4) it means that empty part are only [0;1) and [4;7) and I couldn't place the barbell without squashing the worm. I'm wrong somewhere, please tell me. Hi, I got WA at test #3. I have applied all of the samples above to the algorithm and the program output the correct result. Any body can help me? I meant by above to the samples in the last posts. Here are some tests that helped me pass test number 3: Input: 8 2 4 1 7 0 0 2 3 4 6 6 Output: 2 Input: 10 2 4 1 5 0 1 4 7 8 Output: 3 Input: 20 20 2 1 1 0 Output: 0 Here are some tests that helped me pass test number 3: Input: 8 2 4 1 7 0 0 2 3 4 6 6 Output: 2 Input: 10 2 4 1 5 0 1 4 7 8 Output: 3 Input: 20 20 2 1 1 0 Output: 0 first and second tests are not correct. Worms cross themself. Edited by author 14.03.2010 03:51What this test may contain? I find a solution O(N). On large tests on my PC i get 0.046s at N=100000, but on timus i have TLE... I can send my solution if anybody would be so kind to look at it :) Please try this test.This test helps me a lot. 20 3 2 1 5 1 4 8 12 16 The answer is 0. My step-by-step barbell moving (though improved to add into under and out under the barbell only "right" worms without checking every worm) gives TLE on 8th test. Is segment tree needed? I solved without it.I also used "improved step-by-step barbell moving",but my solution was quite far from TLE. I modeled groove as int array,but if you use sorting on worms array and then search there some coordinates then you can possibly get TLE. Edited by author 06.03.2009 05:20 I solved this problem without sorting. I found difference d[this_step]=count[this_step]-count[prev_step], and after that count_squash_worm=count_squash_worm+d[this_step]. Edited by author 09.03.2009 15:06 If a worm with length 1 has distance 1 from the left edge of the groove, it will be in range from 1cm to 2cm. if we put the barbell with in distance 2 from left side of groove (left edge of left plate lay on coordinate 2 ) does it squash the worm? No, because a worm will be lay in range [1,2) And if just after the barbel? I.e., if the barbel ends at 2, and I put worm at the distance 2, will it squash the worm? |
|
|