For this problem the solution is acceptable when an Integer[] array is used but not when the same algorithm is used with an int[] array. Why? Problem URL:http://www.codeforces.com/problemset/problem/682/B TLE Solution:http://www.codeforces.com/contest/682/submission/19309219 Accepted Solution: http://www.codeforces.com/contest/682/submission/19309197
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Because Arrays.sort() with int[] is using QuickSort that is O(N^2) at worst case.
Arrays.sort() with Integer[] is using MergeSort that is O(N*log(N)) at worst case.
Thank you for the clarification. I will remember this.
This bug should actually be fixed in some version of Java, afaik. You can also apply random shuffle to the array before sorting and it should help with anti-quicksort tests.