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.com/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.com/contest/1073/submission/44858358 can someone suggest the bugs in my code ,if any ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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.com/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 .