Advertisement
Sitleman

Untitled

Dec 24th, 2019
410
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <string>
  7. #include <stack>
  8. #include <tuple>
  9. using namespace std;
  10.  
  11.  
  12. bool ans_sec(int left, int right, string & s, char ind){
  13.  
  14. stack<pair<int, char>> st;
  15. int n = s.size();
  16. int l = 0;
  17. for (int i = left + 1; i <= right + 1; i++){
  18. if (s[i] != s[i - 1]){
  19. pair<int, char> cur = {i - l, s[i - 1]};
  20. l = i;
  21. if (cur.second != ind) {
  22. if (st.size() > 0 && st.top().first > cur.first) {
  23. st.top().first += cur.first;
  24. } else {
  25. st.push(cur);
  26. continue;
  27. }
  28. if (st.size() > 0) cur = st.top();
  29. st.pop();
  30. }
  31. while (st.size() > 0 && (st.top().second == cur.second || st.top().first < cur.first)) {
  32. cur.first += st.top().first;
  33. st.pop();
  34. }
  35. st.push(cur);
  36. }
  37. }
  38.  
  39. if (st.size() > 1 || st.top().second != ind) return false;
  40. else return true;
  41. }
  42.  
  43. bool sol(string & s, string & t){
  44. int l = 0;
  45. int n = (int)t.size();
  46. for (int i = 1; i < n; i++){
  47. if (t[i] != t[i - 1]){
  48. if (s[i] == s[i - 1]) return false;
  49. if (!ans_sec(l, i - 1, s, t[i - 1])) return false;
  50. l = i;
  51. }
  52. }
  53. if (!ans_sec(l, n - 1, s, t[n - 1])) return false;
  54. return true;
  55. }
  56.  
  57. int main(){
  58. ios::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. int q;
  62. cin >> q;
  63. for (int i = 1; i <= q; i++){
  64. string s, t;
  65. cin >> s >> t;
  66. s += "#";
  67. if (sol(s, t)) cout << "Yes\n";
  68. else cout << "No\n";
  69. }
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement