#how can i optimize this code

34 messages · Page 1 of 1 (latest)

ocean nimbus
#

Problem: sort vector of pairs by second in reducing order, if the second's are the same, than sort by first in ascending order; inp, out: 3
20 80
30 90
25 90 ->
25 90
30 90
20 80
My code: ```#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<pair<int, int>> v;
int a, n, b, j;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a >> b;
v.push_back(pair<int, int>(a, b));
}

sort(begin(v), end(v), [](pair<int, int> a, pair<int, int> b)
{ return a.second > b.second; });
for (int i = 0; i < n; i++)
{
if (v[i].second == v[i + 1].second)
{
j = i + 1;
while (v[i].second == v[j].second)
j++;
sort(next(begin(v), i), next(begin(v), j), [](pair<int, int> a, pair<int, int> b){ return a.first < b.first; });
i = j;
}
}

for (auto a : v)
cout << a.first << ' ' << a.second << '\n';
return 0;
}```
how can i make this code faster?

bleak robinBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

ocean nimbus
#

how can i optimize this code

neat monolith
#

the default compariso criteria for std::pair already has this sorting implemented, you don't need a lambda

# 
sort(begin(v), end(v));

that's it

#

the comparison used here is

# 
//return true if left < right
bool compare(const pair<int,int>& left, const pair<int,int>& right)
{
  if(left.first < right.first)
  {
    return true;
  }    
  else if(left.second < right.second)
  {
    return false
  }
  else
  {
    return left.second < right.second;
  }
}
#

this should be the implementation of the default comparison criteria used in std::less<pair<int,int>>::operator(), a.k.a. operator< for the std::pair<int,int>

#

which std::sort uses by default

ocean nimbus
# neat monolith which std::sort uses by default

so, i just need to change to->

using namespace std;
int main()
{
   vector<pair<int, int>> v;
   int a, n, b, j;
   cin >> n;
   for (int i = 0; i < n; i++)
   {
      cin >> a >> b;
      v.push_back(pair<int, int>(a, b));
   }

   sort(begin(v), end(v);

   for (auto a : v)
      cout << a.first << ' ' << a.second << '\n';
   return 0;
}``` ?\
#
  1. Sort by second in decreasing order
  2. Sort parts where seconds are similar by first in ascending order
#

like

#

INP: 2 4 OUT: 2 1
2 3 2 3
2 1 2 4

ocean nimbus
neat monolith
#

so which one is it?

# 
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

how do you want to sort these?

ocean nimbus
#

1 3
2 3
3 3
1 2
2 2
3 2
1 1
2 1
3 1

ocean nimbus
neat monolith
#

right

# 
//return true if left < right
bool compare(const pair<int,int>& left, const pair<int,int>& right)
{
  if(left.second < right.second)
  {
    return true;
  }    
  else if(left.second > right.second)
  {
    return false;
  }
  else
  {
    return left.first < right.first;
  }
}
#

try it

ocean nimbus
#

ok, give me a moment

#

no its not correct as well

#

but changing first 2 conditions helped

#

thanks!

#

but i dont get the second function

#

what does the return false mean

#

how does it work?

bleak robinBOT
#

@ocean nimbus Has your question been resolved? If so, run !solved :)

neat monolith
ocean nimbus
#

thanks!

#

!solved