This is an easier problem that only requires one dimensional array manipulation and careful input parsing.
If
you haven't already, carefully read the problem description before proceeding. First and foremost, we need
to
parse the sample input for the title, author pairs until we reach the first occurrence of END. The format of
each
non-END line will be as follows: title" by author Note the separator string
is
literally " by. We don't want to include the last " character as part
of the
title, as it may affect the sort order. My approach was to use getline as the conditional expression in a
while-loop to read the input up to the first newline character, breaking when the extracted contents matched
string literal END. For each line containing a title-author pair, I use string find to search the string for
the
given string separator, split the string using string substr, and store the pair.
Note we are storing the pair in author-title order to get the benefits of built-in sorting mechanism of pair within a set. Although I chose to insert each pair into a set, you could also use a vector of pairs, and call sort on it upon breaking the while-loop. However, you may not use a map to store the pairs in author-title order. Take a moment to consider why this approach cannot work. To keep it simple, I chose to store the information associated with title, author, and state (i.e. on-shelf, off-shelf, pending-return) each in its own one-dimensional array, ordered appropriately.
Next, we need to read line by line and perform operations based on line format. We stop processing more lines when we reach the END line. There are three formats:
We can parse this in a number of ways. Since your choice of how to process input will rarely, if ever,
result in
TLE you are free to
use whatever method is fastest to code or easiest to visually verify correctness. If you ever do a getline
after
reading with cin
>> ..., you must issue a cin.ignore() to remove the newline character
from
the input stream. cin will leave trailing whitespace
in the stream, so if you don't clear it before a getline you could end up with an empty string you didn't
expect.
Moving on... I read
the next word with cin, breaking if the contents match END. If the contents match BORROW or RETURN, I read
the
next word (remembering
to consume the trailing whitespace left from cin), trim it appropriately, and use the find function
template,
included with the
<algorithm> header, to get an iterator to the matching element in my title vector. This is an iterator
of
type
vector<string>::iterator, but we can convert it to a 0-based index by
subtracting the begin() container iterator from it.
Once we hit the SHELVE command, we iterate over all elements of the st vector, and for each element where
st[i] == 2, we need to
output one line indicating what book the ith book should be placed after (with a special case when it is the
first
book in the shelf
order).
My print() function, used in the SHELVE block above:
That's it! These problems are great practice for beginners since they get practice using getline and cin together. It is far better to make mistakes in practice and correct them, than to be confused in a contest environment over a language construct.