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?
how did you guys got to know your marks??
also i want to know that i compiled and run my program for many test cases and it worked alright but during submission of code system took more time to check the code and finally it showed that it doesnāt pass all the test cases. does it mean that i m not going to get any marks for that program???
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) ?
@hackpert I solved it using Priority Queues.
The idea is that you must have realized that the optimal split is such that the smallest N/2 numbers are in one list and the largest N/2 numbers in the other.
So there were two cases, you could either keep swapping the min in A with the max in B, or vice versa (upto K times). Now It was necessary to get the min of A (and max of B) after swap operations, so I used a Priority Queue. This approach is O(NlogN).
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.
In 2nd question my solution was n*10^5 and then an n^2 dp so there are chances that it can fail on larger test inputs.Also i want to know whether K can be equal to N in 1st question as N distinct swaps would mean just interchanging the 2 arrays?