Блог пользователя Qualified

I should not get TLE.
Автор Qualified, 4 года назад, По-английски

I am solving 181B - Number of Triplets. With the constraints being $$$n <= 3000$$$ and my solution supposedly running in $$$O(n^{2})$$$. Am I missing something? 88909110.

  • Проголосовать: нравится
  • -37
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Map with key of pair<long double, long double> would be slow, though still surprised it TLE's (actually on second thought I'm not, it is like O(n^2lgn) with rlly bad constant factor. Plug in 3000). Don't divide coordinates by 2, just multiply all coordinates by 2, and no need to work with doubles, and try not to use map in the first place (constraints are small). In general, try to avoid doubles, they are slow, and use array when you can.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Since you are using map it's $$$O(n^2 \log n)$$$. Also float arithmetic consumes huge constant factor, that's probably why you are getting TLE.

→ Ответить