Code - единия ми тест гърми
In the far future, the citizens of Europa (the Jupiter moon, not the continent) decide to ban the use of links to websites, without the express permission of the owners of said websites (of course, this is a fictional story, and any correlations to actual people or events is purely accidental). The Internet community on the planet, however, did not really like this new law, so they found a way around it – they started communicating through a special code that couldn’t be read by the lawmakers.
You work for the government of Europa, and you are tasked with analyzing the coded messages. What the government knows about the code so far, is that each message it consists of a sequence of non-negative integer numbers. The sequence is separated into “parts” – some of the integer values in the sequence are consider separators, and every value that is not a separator is an element of a part. A part is simply a sequence of values (non-separators), starting after a separator (or at the start of the sequence), and ending before a separator (or at the end of the text).
To do your analysis, you need some software that, given a message as a sequence of integers, and given search values, counts how many total parts contain each of those values. If multiple identical parts (same length, with the same values, in the same order) contain a value, count all of them (i.e. we are not searching for unique parts containing a value, but for all parts containing it).
Luckily, you know a thing or two about programming, so you will write that software yourself… well, what are you waiting for?
Input
The first line of the standard input will contain a sequence of non-negative integer values - the separators.
The second line of the standard input will contain a sequence of non-negative integer values, separated by single spaces – the message.
The following lines of the standard input will contain the search values – positive integers, each on a single line.
The last line of the standard input will contain the value 0 – this is not a search value (and no search value will be 0) – it is an indicator that the program should stop reading input.
Output
For each of the entered search values, print a single line containing the number of parts that contain that search value.
Restrictions
There will be no more than 30000 values in the message.
There will be no more than 40000 searches.
There will be no search for the value 0, but there could be searches for values that are not contained in any part.
The total running time of your program should be no more than 0.2s
The total memory allowed for use by your program is 16MB
https://pastebin.com/dyE10E6P
Всъщност, гърмяха ми два теста, но единия беше за време. Надявам се time limit - a да съм го оправил след като използвах двоично търсене, но няма как да го проверя защото задачата не е активна в judge. Но така или иначе, ми гърмеше още един тест. Надявам се да ми помогнете за него. Явно пропускам нещо.
Много благодаря за препоръките и за това, че ми показахте коя проверка пропускам. Наистина много съм усложнил логиката. Няма смисъл да разделям съобщението на отделните групи и да проверявам всяка група. Достатъчно е да знам всяко число колко пъти се повтаря в съобщението. В условието не е казано, че може да има повече от едно value в група, т.е. ако знам колко пъти се повтаря едно value в съобщението значи в толкова групи участва. Благодаря и за метода, който ми показахте, за по-бързо четене на входа. Четох, че има и друг начин за развързване на С и С++ потоците : cin::sync_with_stdio(false), но честно казано не можах да разбера каква е разликата между двата метода и кой кога се използва.
Съобщението трябва да се обработи по групи, защото от примера, който е даден към услвието, се вижда, че дадено число може да се среща и повече от веднъж групата:
32 115 101 113 117 101 110 99 101 32
Имайте предвид, че понякога има проблеми при използването на cin::sync_with_stdio(false) - не се прочитат напълно входните данни, примерно.
https://pastebin.com/wks54nwM
Това измислих като следвах вашите упътвания, за които благодаря. Разбира се, може и да не съм ги разбрал правилно. Имам един въпрос: Не е ли по-добре да използвам обикновен map и да търся в него с lower_bound метода отколкото да използвам unordered_map и обикновено търсене? Т.е. кое търсене е по-бързо, нормално търсене в unordered_map или lower_bound търсене в обикновен map?
Не.
lower_bound за map има сложност O(lg(N)), докато find в unordered_map има константна сложност (О(1)), т.е. за контейнер с 30000 елемента търсенето в unordered_map ще е близо 15 пъти по-бързо.
Благодаря за информацията. Тези неща би трябвало да ги знам, но ето кой не е внимавал в час... Много ми помагате! Благодаря отново!