"Camera Purchase" challenge Here is the text of the problem:


  There are 5 brands of cameras sold on your website – Nikon, Canon, Sigma, Fujifilm and Sony. Each of these brands sell different cameras at distinct prices. For simplicity, each brand is represented by an integer between 1 to 5. Your website has q shoppers each of whom has a list of brands they are willing to buy from. Based on every user's buying history, you know that they are most likely to buy the kth cheapest camera amongst the brands they like. Your task involves finding this kth cheapest camera for each shopper.
  
  Given a list of brands and the prices of their cameras, the list of shoppers and their preferences, for each shopper, determine the kth cheapest camera. If no such camera exists, print -1.
  
  Input Format
  
  The first line contains integer n denoting the total number of cameras being sold. The second line contains an array of n integers describing the brands of the cameras. The third line contains an array of n integers describing the prices of those particular cameras.
  
  After that, q queries describing the shoppers' preferences follow. A single query is described in 3 lines.
  
  
  d represents the number of brands the shopper will buy from.
  d space separated integers in ascending order denoting the index of the brands.
  kth cheapest camera to display.
  
  
  Constraints
  
  
  1 ≤ n ≤ 105
  1 ≤ q ≤ 105
  1 ≤ pricesi ≤ 109
  1 ≤ brandsi ≤ 5
  1 ≤ lj ≤ 5
  1 ≤ k ≤ 5 * 105
  all pricesi are distinct
  
  
  Output Format
  
  Output exactly q lines. In the jth of them print a single integer denoting the price of the camera lens the jth shopper will buy. If no such lens exists, print -1.


Here is my solution: 

#include &lt;cmath&gt;
#include &lt;cstdio&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;unordered_map&gt;
using namespace std;

int main() {  
    int n;
    cin &gt;&gt; n;
    vector&lt;int&gt; brands;
    for (int i = 0; i &lt; n; i++){
        int tmp;
        cin &gt;&gt; tmp;
        brands.push_back(tmp);
    }

    unordered_map&lt;int, vector&lt;int&gt;&gt; dict;
    for (int i = 0; i &lt; n; i++){
        auto it = dict.find(brands[i]);
        if( it == dict.end() ) {
        dict.insert({brands[i], vector&lt;int&gt;()});
        }
    }
    for (int i = 0; i &lt; n; i++){
        int tmp;
        cin &gt;&gt; tmp;
        dict[brands[i]].push_back(tmp);
        }

    int q;
    cin &gt;&gt; q;
    for (int i = 0; i &lt; q; i++){
        int number_of_brands;
        cin &gt;&gt; number_of_brands;
        vector&lt;int&gt; indexes;
        for (int i = 0; i &lt; number_of_brands; i++){
            int tmp;
            cin &gt;&gt; tmp;
            indexes.push_back(tmp);
            }
        int k;
        cin &gt;&gt; k;
        vector&lt;int&gt; potential_cameras;
        for (auto i : indexes){
            for (auto x : dict[i]){
                potential_cameras.push_back(x);
                }
            }
        sort(potential_cameras.begin(), potential_cameras.end());
        if (potential_cameras.size() &gt;= k){
            cout &lt;&lt; potential_cameras[k - 1] &lt;&lt; '\n';
            }
        else {
            cout &lt;&lt; -1 &lt;&lt; '\n';
        }
    }
    return 0;
}


This algorithm times out for every single one of the bigger sized test cases. It is one of my very first attempt at writing C++ code, so please be merciless with any bad habit or code smell you can spot, but in this specific case I am curious to know what the main issue is, and if I could have used more suitable data structures than the ones I chose.
vector&lt;int&gt; potential_cameras;
        for (auto i : indexes){
            for (auto x : dict[i]){
                potential_cameras.push_back(x);
                }
            }
        sort(potential_cameras.begin(), potential_cameras.end());



Let's review the important constraints:


At most 5 brands
At most 10000 cameras
Up to 10000 queries


So this code is executed up to 10000 times, and each time is filtering up to 10000 cameras and then sorting up to 10000 cameras.

Given that each query includes at least one brand out of the five, there are only 31 possible brand combinations. So by pre-computing you could execute this code 31 times rather than 10000 times, and since it's the obvious candidate for the bottleneck that might give you a 300-times speedup.

If that's still not fast enough, then you need to look at linear time median algorithms. But frankly if the queries are evenly distributed then ~300 queries per brand combination is much larger than \$\lg 10000 \approx 13\$, so it's probably faster to quicksort once per combination than to execute a linear time median once per query. If you really want to overkill it then you could create a custom data structure which supports multiple median queries by maintaining state of which ranges of the array have been partitioned around which pivot, but KISS, YAGNI.

Alternatively, but still violating KISS, you could do just five sorts (one per camera) and then some complicated multiple binary chop. I'd still prefer one sort per brand combination.