fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Word {
  6.     string s;
  7.     int index;
  8.     bool operator < (Word o) const {
  9.         return s < o.s;
  10.     }
  11. };
  12.  
  13. int const WMAX = 1000000;
  14. int const NMAX = 1000;
  15. int w, n;
  16. Word d[1 + WMAX];
  17.  
  18. bool isPrefix(string a, string b) {
  19. 	if(b.length() < a.length()) return false;
  20. 	return (b.substr(0, a.length()) == a);
  21. }
  22.  
  23. int binarysearch(int from, int to, string val) {
  24. 	//cout << "checking: " << val << ", " << from << " <-> " << to << "\n";
  25.     if(from < to) {
  26.         int guess = (from + to)/2;
  27.         if(val <= d[guess].s) {
  28.             return binarysearch(from, guess, val);
  29.         } else {
  30.             return binarysearch(guess+1, to, val);
  31.         }
  32.     }
  33.     return from;
  34. }
  35.  
  36. int main() {
  37.     cin >> w >> n;
  38.     for(int i = 1; i <= w; i++) {
  39.         cin >> d[i].s;
  40.         d[i].index = i;
  41.     }
  42.     sort(d+1, d+w+1);
  43.     /*for(int i = 1; i <= w; i++) {
  44.     	cout << d[i].s << "\n";
  45.     }*/
  46.     for(int i = 1; i <= n; i++) {
  47.         int k;
  48.         string pre;
  49.         cin >> k >> pre;
  50.         int ans = binarysearch(1, w, pre);
  51.         //cout << "here: " << ans << " " << k << "\n";
  52.         ans += k-1;
  53.         if(ans > w || !isPrefix(pre, d[ans].s)) {
  54.             cout << -1 << "\n";
  55.         } else {
  56.             cout << d[ans].index << "\n";
  57.         }
  58.     }
  59. }
Success #stdin #stdout 0.02s 42584KB
comments (?)
stdin
copy 
7 3
ethan
ernest
a
acb
abb
accepted
acc
4 a
3 ac
4 e
stdout
copy 
7
6
-1
https://ideone.com/8AI4MB
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!