"Music Your Way" Sorting Problem

Problems and Contests
#1

My code for the Kattis problem “Music Your Way” is included below. Of the 4 test cases, I pass the first two tests but receive a Wrong Answer on the third test. I would appreciate it if you can provide small nudges to help me realize my own mistakes. Please guide me to my errors rather than revealing them yourselves.

#include <bits/stdc++.h>
using namespace std;

int N, M; // M = # songs, N = # sort commands
vector<string> attributes; // only for printing attributes
unordered_map<string, int> convert; // map attribute to index
vector<vector<string>> songs;

void read() {
  //read attributes
  int indx = 0;
  string s, temp;
  getline(std::cin, s); stringstream X(s);
  while(getline(X, temp, ' ')) {
     attributes.push_back(temp);
     convert[temp] = indx++;
  }
  //read songs
  cin >> M; songs.resize(M);
  for (int i = 0; i < M; i ++) {
    for (int j = 0; j < indx; j ++) {
      cin >> s;
      songs[i].push_back(s);
    }
  }
}

void commands() {
  cin >> N;
  string sort_by;
  while (N--) {
    cin >> sort_by;
    sort(songs.begin(), songs.end(), [=](vector<string> a, vector<string> b) -> bool {
      return a[convert[sort_by]] < b[convert[sort_by]];
    });
    //print attributes
    for (string a : attributes) {
      cout << a << " ";
    }
    cout << endl;
    //print songs
    for (auto vs : songs) {
      for (string val : vs) {
        cout << val << " ";
      }
      cout << endl;
    }
    cout << endl;
  }
}

int main()
{
    read();
    commands();
}

Thank you!

#2

(complete guess) could it be because you have to sort based on the previous attribute(s) if the current attribute is the same?

#3

I believe the std::sort() function in C++ already does that. It defaults to the pre-existing order when the parameters to compare are the same.

#4

No, that’s what std::stable_sort does.

#5

Thank you. I found that std::sort uses introsort while std::stable_sort uses merge sort (which by its recursive definition preserves the original order).

#6

Let a and b be indices between 0 and N.
Your post makes me wonder what the difference is between the following:

sort(all(vec), [&](int a, int b) {
    return arr[a] < arr[b];
});

and

sort(all(vec), [&](int a, int b) {
    return arr[a] <= arr[b];
});

I thought the comparator decides whether to place a before b. Does the = condition make a difference?

#7

Yes.