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

TLE because of sort using rbegin
Автор abba5, история, 4 года назад, По-английски

I was trying to submit this -> Remove Max Number of Edges to Keep Graph Fully Traversable question.
but I got TLE because of sort using rbegin 

sort( edges.rbegin(), edges.rend())

but after change with comparator funtction code got accepted. 

sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
            return a[0] > b[0];
        });

Submission Using rbegin

Submission Using comparator

I tried to run this in local and got similar performance but when I used some different build command I got 2x time difference for $$$N = 10^5$$$

Build command:

  1. g++ a.cpp

  2. g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp

output using 1st build command:

0.0290290006s
0.0652360022s

output using 2nd build command:

0.9816750288s
2.1033749580s

Following code I used for bench-marking.

Bench-marking code

Can anyone explain why this time difference happening?
Will this happen in code-forces also?

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

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

same thing happened to me last month..... was using sort(vector.rbegin(),vector.rend()) and got tle.....after the contest i used sort(vector.begin(),vector.end(),greater()) and then got AC... i used to thought that complexity of both sorting is same

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

Can anyone explain why this time difference happening?

It is happening because you have used the compile flags without knowing what they do.
-D_GLIBCXX_DEBUG: it inserts some debug / sanity checks that can really slow your code down. For example, you may get $$$O(n)$$$ complexity for std::binary_serach.
And you forgot the most important flag -O2. With -O2 both of them takes same time.

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

That's why I prefer using comparators

→ Ответить