What is a faster way to sort these string inputs based on their position in the sentence?

user_10855531 0
Viewed 71

Practicing for the national Olympiad of Informatics stumbled a problem that goes as follows: The user inputs the amount of words (n) in the sentence and the proceeds on entering the words along with their positions separated by a space. You are asked to input the sentence with the correct order of words.

For example:

Input:

4
this 1
sentence 4
is 2
a 3

Output:

this is a sentence

Restrictions:

1 <= N <= 3 * 10^5
1 <= Size of a word <= 50

I have tried to solve this problem using an unordered_map and it turns out is solves this pretty fast taking only 0.588 seconds going over all the test cases which made my solution the 5th fastest out of 45. However the fastest solution only takes 0.14 seconds to compute and I can't figure out how he/she did it. What is a faster way to solve this problem than using unordered_map?

unordered_map < int, string > words;    
int n;    
cin >> n;  
for (int i = 0; i < n; i++) {    
    string word;    
    int position;     
    cin >> word >> position;    
    words[position] = word;    
}    
for (int i = 1; i <= n; i++) {     
    cout << words[i] << "\n";      
}
optimization c++
1 Answers

std::unordered_map is a little overboard for this problem. Since you are provided the order that the elements will be in you can get away with a std::vector<std::string>, and you just put the elements in the vector where the input tells you. That simplifies the program code to

int main()
{
    int records;
    std::cin >> records;
    std::vector<std::string> sentence(records);
    std::string word;
    int place;
    while (std::cin >> word >> place)
        sentence[place - 1] = std::move(word); // subtract one as input is 1 based index, use move to save an allocation and copy
    for (auto const& e : sentence)
        std::cout << e << " ";
}
user_43424980
Related