fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 1e6+5;
  4.  
  5. int n, a[maxN], b[maxN];
  6. string s, t;
  7.  
  8. void solve()
  9. {
  10. 	stack<int>st, st1;
  11. 	for(int i=1; i<=n; i+=1)
  12. 	{
  13. 		if(s[i] == '(') st.push(i);
  14. 		else
  15. 		{
  16. 			a[i] = st.top();
  17. 			a[st.top()] = i;
  18. 			// cout<<i<<" "<<st.top()<<'\n';
  19. 			st.pop();
  20. 		}
  21. 	}
  22. 	for(int i=1; i<=n; i+=1)
  23. 	{
  24. 		if(t[i] == '(') st1.push(i);
  25. 		else
  26. 		{
  27. 			b[i] = st1.top();
  28. 			b[st1.top()] = i;
  29. 			// cout<<i<<" "<<st.top()<<'\n';
  30. 			st1.pop();
  31. 		}
  32. 	}
  33. 	// for(int i=1; i<=n; i+=1) cout<<b[i]<<" "; cout<<'\n';
  34. 	int dem0 = 0, dem1 = 0;
  35. 	for(int i=1; i<n; i+=1)
  36. 	{
  37. 		if(a[i] == i+1) dem0++;
  38. 		if(b[i] == i+1) dem1++;
  39. 	}
  40. 	if(dem0 != dem1)
  41. 	{
  42. 		cout<<"NO\n"; return;
  43. 	}
  44. 	dem0 = 0; dem1 = 0;
  45. 	if(s[1] == '(' && a[1] == n)
  46. 	{
  47. 		dem0++;
  48. 		int id = n-1;
  49. 		for(int i=1; i<n; i+=1)
  50. 		{
  51. 			if(s[i] == '(' && s[i+1] == '(')
  52. 			{
  53. 				if(a[i+1] == id) dem0++;
  54. 				id--;
  55. 			}
  56. 			else break;
  57. 		}
  58. 	}
  59. 	if(t[1] == '(' && b[1] == n)
  60. 	{
  61. 		dem1++;
  62. 		int id = n-1;
  63. 		for(int i=1; i<n; i+=1)
  64. 		{
  65. 			if(t[i] == '(' && t[i+1] == '(')
  66. 			{
  67. 				if(b[i+1] == id) dem1++;
  68. 				id--;
  69. 			}
  70. 			else break;
  71. 		}
  72. 	}
  73. 	// cout<<dem0<<" "<<dem1<<'\n';
  74. 	if(dem0 != dem1)
  75. 	{
  76. 		cout<<"NO\n"; return;
  77. 	}
  78. 	cout<<"YES\n";
  79. }
  80.  
  81. int main() {
  82. 	int test;
  83. 	cin>>test;
  84. 	while(test--)
  85. 	{
  86. 		cin>>n>>s>>t;
  87. 		s = '0'+s;
  88. 		t = '0'+t;
  89. 		for(int i=0; i<=n; i+=1) a[i]=b[i]=-1;
  90. 		solve();
  91. 	}
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 5652KB
comments (?)
stdin
copy 
5
4
()()
()()
4
()()
(())
6
(())()
()(())
8
(()()())
()()(())
8
()()(())
()(()())
stdout
copy 
YES
NO
YES
NO
YES
https://ideone.com/zK9wjK
language:
C++ (gcc 8.3)
created:
15 hours 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!