Вызов lower_bound:
В pos находим (дихотомией) в отсортированном словаре пар dict
позицию слова пары со словом pref.
14_FebB. AUTO
http://dl.gsu.by/task.jsp?nid=1270623&cid=15
Идея решения, вводим словарь и по ходу заносим в вектор слова и номера этих слов в словаре.
Сортируем слова по возрастанию (вместе с номерами).
Цикл по поисковым префиксам
Вводим префикс и его позицию k
Дихотомией (с помощью lower bound)
ищем в словаре pos первое вхождение префикса
Инкрементируем pos на k
Если полученная позиция в словаре,
а слово на этой позиции совпадает с префиксом
Тогда выводим её
Иначе выводим -1
Подробнее о коде
В pos находим (дихотомией) в отсортированном словаре позицию слова pref.
если k-ое вхождение есть и соответствует pref,
тогда выводим исходный номер слова
иначе вводим -1
Соответствие слова из словаря word и искомого префикса pref
Выясняется с помощю булевой функции match
Далее приведен полный текст решения
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<string, int> > dict;
bool match(string& pref, string& word)
{
if (pref.size() > word.size()) return false;
return word.substr(0, pref.size()) == pref;
}
int main()
{
freopen("auto.in", "r", stdin);
freopen("auto.out", "w", stdout);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
dict.push_back(make_pair(s, i));
}
sort(dict.begin(), dict.end());
for (int i = 0; i < m; i++)
{
int k; string pref;
cin >> k >> pref;
k--;
int pos = lower_bound(dict.begin(),
dict.end(),
make_pair(pref, 0))
- dict.begin();
int poss = pos + k;
if (poss < dict.size() && match(pref, dict[poss].first))
cout << dict[poss].second + 1 << endl;
else cout << -1 << endl;
}
}