lower_bound - DL Руководство пользователя

Вызов lower_bound:

&nbsp; &nbsp; &nbsp; int pos = lower_bound(dict.begin(),&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dict.end(),
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; make_pair(pref, 0))&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - dict.begin();

В pos находим (дихотомией) в отсортированном словаре пар dict
позицию слова пары со словом pref.

14_FebB. AUTO
http://dl.gsu.by/task.jsp?nid=1270623&cid=15

Идея решения, вводим словарь и по ходу заносим в вектор слова и номера этих слов в словаре.
Сортируем слова по возрастанию (вместе с номерами).
Цикл по поисковым префиксам
Вводим префикс и его позицию k
Дихотомией (с помощью lower bound)
ищем в словаре pos первое вхождение префикса
Инкрементируем pos на k
Если полученная позиция в словаре,
а слово на этой позиции совпадает с префиксом
Тогда выводим её
Иначе выводим -1

Подробнее о коде

&nbsp; &nbsp; &nbsp; int pos = lower_bound(dict.begin(),&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dict.end(),
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; make_pair(pref, 0))&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - dict.begin();

В pos находим (дихотомией) в отсортированном словаре позицию слова pref.

&nbsp; &nbsp; &nbsp; int poss = pos + k;
&nbsp; &nbsp; &nbsp; if (poss < dict.size() && match(pref, dict\[poss\].first))
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cout << dict\[poss\].second + 1 << endl;
&nbsp; &nbsp; &nbsp; &nbsp; else cout << \-1 << endl;

если k-ое вхождение есть и соответствует pref,
тогда выводим исходный номер слова
иначе вводим -1

bool match(string pref, string word)
&nbsp; {
&nbsp; &nbsp; if (pref.size() > word.size()) return false;
&nbsp; &nbsp; return word.substr(0, pref.size()) == pref;
&nbsp; }

Соответствие слова из словаря word и искомого префикса pref
Выясняется с помощю булевой функции match

Далее приведен полный текст решения

all.cpp

\#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<string, int> > dict;

bool match(string& pref, string& word)
&nbsp; {
&nbsp; &nbsp; if (pref.size() > word.size()) return false;
&nbsp; &nbsp; return word.substr(0, pref.size()) == pref;
&nbsp; }

int main()&nbsp;
{
&nbsp; freopen("auto.in", "r", stdin);
&nbsp; freopen("auto.out", "w", stdout);
&nbsp; cin >> n >> m;
&nbsp; for (int i = 0; i < n; i++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; string s;
&nbsp; &nbsp; &nbsp; cin >> s;
&nbsp; &nbsp; &nbsp; dict.push_back(make_pair(s, i));
&nbsp; &nbsp; }
&nbsp; sort(dict.begin(), dict.end());
&nbsp; for (int i = 0; i < m; i++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; int k; string pref;
&nbsp; &nbsp; &nbsp; cin >> k >> pref;
&nbsp; &nbsp; &nbsp; k--;
&nbsp; &nbsp; &nbsp; int pos = lower_bound(dict.begin(),&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dict.end(),
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; make_pair(pref, 0))&nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - dict.begin();
&nbsp; &nbsp; &nbsp; int poss = pos + k;
&nbsp; &nbsp; &nbsp; if (poss < dict.size() && match(pref, dict\[poss\].first))
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cout << dict\[poss\].second + 1 << endl;
&nbsp; &nbsp; &nbsp; &nbsp; else cout << \-1 << endl;
&nbsp; &nbsp; }
}