fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3.  
  4. using namespace std;
  5.  
  6. priority_queue< pair<int,char> > q;
  7. string s, p; 
  8. int a[200005];
  9. int n;
  10.  
  11. int ktra(){
  12. 	int m = p.size();
  13. 	int count = 0;
  14. 	while (!q.empty()){
  15. 		pair<int,char> temp = q.top();
  16. 	//	cout << temp.first << " " << temp.second << endl;
  17. 		q.pop();
  18. 		if (temp.second == p[count]){
  19. 		//	cout << temp.first << " " << temp.second << endl;
  20. 			count++;
  21. 		}
  22. 		if (count == m){
  23. 			//cout << "1" << endl;
  24. 			return 1;
  25. 		}
  26. 	}
  27. 	//cout << "0" << endl;
  28. 	return 0;
  29. }
  30.  
  31. int main(){
  32. 	cin >> s >> p;
  33. 	n = s.size();
  34. 	for (int i = 0; i < n; i++){
  35. 		cin >> a[i];
  36. 	}
  37. //	if (s.substr(s.size()-p.size(),p.size()) == p){
  38. //		cout << s.size() - p.size();
  39. //		return 0;
  40. //	}
  41. 	int l = 1, r = n;
  42. 	while(l<=r){
  43. 		while(!q.empty()) q.pop();
  44. 		int mid = (r+l)/2;
  45. 		for (int i = mid; i <= n; i++){
  46. 			q.push(make_pair(-a[i],s[a[i]-1]));
  47. 		}
  48.  
  49. 		//cout << "l: " << l << " r: " << r << " mid: " << mid << endl;
  50. 		if (ktra()) l=mid+1;
  51. 		else r=mid-1;
  52. 		//cout << "l: " << l << " r: " << r << "	 mid: " << mid << endl;
  53. 		//system("pause");
  54. 	}
  55. 	cout << r;
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 16848KB
comments (?)
stdin
copy 
ababcba
abb
5 3 4 1 7 6 2
stdout
copy 
3
https://ideone.com/igmDZ6
language:
C++ (gcc 8.3)
created:
9 years 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!