in the educational Codeforces Round 53 , problem B (1073B) my solution gives TLE ,but I don't think it should. My submission is : http://codeforces.me/contest/1073/submission/44858358 can someone suggest the bugs in my code ,if any ?
in the educational Codeforces Round 53 , problem B (1073B) my solution gives TLE ,but I don't think it should. My submission is : http://codeforces.me/contest/1073/submission/44858358 can someone suggest the bugs in my code ,if any ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Try adding this line in the beginning of the main function: ios_base::sync_with_stdio(false);
Yes , it worked . Thanks for the reminder . Usually I use fast io but on codeforces ,it didn't seem necessary . Still, I am astonished how slow cin ,cout actually is. Thank you again.
One way to speed up your program and get accepted even without using ios_base::sync_with_stdio(false); is to just do all input reading in one go.
With ios_base::sync_with_stdio(false); 748 ms
Without ios_base::sync_with_stdio(false); and reading all input in one go: 514 ms
With ios_base::sync_with_stdio(false); and reading all input in one go: 124 ms
I didnt realize it would be this slow. Thanks a lot .
first of all your code is not in O(n) but in expected O(n) wich may or maybe not be a huge difference since there could be hash collision test... (but i dont know)
and second why using a hashmap at all when you know that the input is a permutation? you can just use an array?
and another issue is reading the input just partly... this seems to be quite slow: https://codeforces.me/contest/1073/submission/44907426
I even used an array instead of hashmap. Still ,I was getting tle. Now I know where I slowed things down, I actually used a global array(size 2e5+5) for hashing . The memset must have slowed things down . Thanks for the vector illustration .