How can this code pass in 1 second time limit

Revision en1, by sachinjaiswal, 2022-10-15 21:45:34

This is the code (https://codeforces.net/contest/1746/submission/176340285) of one of the contestant in my room of global round 23. And I think it should result in TLE(Correct me if I'm assuming something wrong). As you can see he used l.pop(idx_i) inside his second while loop of his sort function and the time complexity of pop function is O(N), when it is performed on any arbitrary index.

Here is the testcase which can make his code go TLE :-

2

100000

1 1 1 ... till 50000 places + 0 0 0 ... till 100000 places

100000

1 1 1 ... till 50000 places + 0 0 0 ... till 100000 places

Tags tle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sachinjaiswal 2022-10-15 21:45:34 684 Initial revision (published)