MiyawakiSakura's blog

By MiyawakiSakura, history, 16 months ago, In English

Hi everyone, I have been working on what originally seemed to me both in the contest and even now a really simple problem, but I haven't been able to solve it even after looking at someone else's program. The problem is making me angry enough to tank the grey downvotes since I really have no clue what else I can fix about my program.

Here is my submission: https://codeforces.me/contest/1846/submission/214439016 And here is the person I am looking at's submission: https://codeforces.me/contest/1846/submission/212618879

Can someone explain to me what I am missing? I think it has something to do with passing or creating arrays as far as I can tell. If I change my array of positions "res" to a 2d ArrayList and pass around rows of it, I time out on an earlier test case. Can someone please take a look and let me know what I am missing?

Also, just looking at the case I fail on, it seems like it has something to do with sorting a singular really long array, but the math works out to less than 10^8 so I must be missing something big.

Thank you in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Update: Turns out the test cases are just really hostile to java. Check out this amazing blog to avoid these pitfalls: https://codeforces.me/blog/entry/116603

TLDR: Quicksort on primitives can be hacked, fix with ruffle sort or using Integer/Long wrapper classes