O(10^8) should pass.
BTW, logn could have been reduced by storing the index in an array, since all the elements were unique.
2 Likes
Try running your code on input of N = 2500, A = {1, 2, 3, …, 2500}. If your code works under 1 second, then you should be fine.
It ran within a second! 
But I feel I made a few mistakes, like not setting temp to 0 or 1 at the end of each j loop.
EDIT: The temp thing doesn’t make any difference.
I believe that’s not the worst case @sampritipanda
Something like 1, 4, 9, 16… where the answer is not high, will probably be the worst case… Mine takes more than 1 sec for that…
Btw, what were the constraints on length? 1 <= l <= 10^5 right?
Length is 0 <= l <= 10^5. What was the exact test case where your codes takes more than 1 second?
Sorry for typo. I knew its 2.5*10^8, but it should work I guess, because one codeforces and ideone, it takes 0.6 seconds or so, to run. Hence if you guys had O(n^2) algorithm, and they keep the TL even 1 sec, it has huge chance of passing. Cheer up, otherwise you could personally request them this. 
What? what? How did you get time for such heavy duty local testing of your code? And whats your expected score? did your computer work fine at the Delhi centre??
1 Like
Sorry but it means you’re program gives wrong answer for some case(s).
Yes, it means 0.
Yep, I was pretty surprised. I don’t expect it will pass once they test on larger inputs though.
So you’re expecting 100 now? Or did you optimise for O(n^2) ?
No I’m expecting 140, as O(N^3) should run on the first subtask of Bamboo Art (it was N <= 400).
1 Like
The first computer I got worked perfectly fine. But, around 2:15 minutes into the exam, I pressed Ctrl+F and got locked out. They switched me to another computer but it didn’t have g++ installed. After trying to explain the problem to them for several minutes, I just gave up and left (I didn’t have my code in the new computer (and Ctrl+C was not working on the submitted code) so it was anyway useless). If I didn’t do anything stupid in the first one I should get at least 100. I have got a vector index out of bounds in problem 2 so if the grading server is strict, it might crash (on all cases).
1 Like
@nibnalin About the testing, the IDE was displaying the execution time after the program had stopped so I just set N to 2500 and the lengths to 0,1,2,…,2499. It was not quite accurate but it did give some idea. By the way, how much are you expecting?
1 Like
@AnonymousBunny was sort of trying that out, maintain two arrays and objective is to get the bigger elements into one array and smaller into the other. i.e., for every i till n cases, a[i] >= b[i]. this is of course only till no. of swaps can be carried out. but couldnt write this efficiently.
It was just my computer, that was slow. It ran within 1 sec on codechef’s server. The test case was randomised, taking care that no number repeats.
Btw, do you know how fast the server that IARCS will use for testing is?
@srijon Lucky you. I had to change computers 4 times. Finally the 5th one I got was good enough, but really bad keyboard plus really slow, but whatever, I had only 100 minutes or so after all the changing. So I used them to the best I could, and am expecting 130 now. I coded the one for 2nd subtask of problem 1, but was getting WA, and had only 5 minutes or so left, so decided to let it go and leave. The centre etc. was really really poor.
Yes, as far as I remember K was <= N for 2nd subtask