fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdint>
  4. #include <tuple>
  5. #include <algorithm>
  6. typedef std::tuple<std::uint64_t, std::uint64_t> RData;
  7.  
  8.  
  9. bool ErasePairOne(std::string& S) {
  10. 	std::size_t i = 0;
  11. 	std::size_t j = 0;
  12.  
  13. 	for (i = 0; i < S.size(); i++) {
  14. 		if (S[i] == '(')break;
  15. 	}
  16. 	for (j = i; j < S.size(); j++) {
  17. 		if (S[j] == ')')break;
  18. 	}
  19.  
  20. 	if (j == S.size())return false;
  21.  
  22. 	S.erase(S.begin() + j);
  23. 	S.erase(S.begin() + i);
  24. 	return true;
  25. }
  26.  
  27. bool LTurnEraseOneL(std::string& S) {
  28. 	auto it = std::find(S.begin(), S.end(), '(');
  29. 	if (it == S.end())return false;
  30.  
  31. 	*it = ')';
  32. 	return ErasePairOne(S);
  33. }
  34. bool LTurnEraseOneR(std::string& S) {
  35.  
  36. 	auto it = std::find(S.rbegin(), S.rend(), '(');
  37. 	if (it == S.rend())return false;
  38.  
  39. 	*it = ')';
  40.  
  41. 	return ErasePairOne(S);
  42. }
  43. bool RTurnEraseOneL(std::string& S) {
  44. 	auto it = std::find(S.begin(), S.end(), ')');
  45. 	if (it == S.end())return false;
  46.  
  47. 	*it = '(';
  48. 	return ErasePairOne(S);
  49. }
  50. bool RTurnEraseOneR(std::string& S) {
  51.  
  52. 	auto it = std::find(S.rbegin(), S.rend(), ')');
  53. 	if (it == S.rend())return false;
  54.  
  55. 	*it = '(';
  56.  
  57. 	return ErasePairOne(S);
  58. }
  59. bool PairTurnEraseOne(std::string& S) {
  60. 	std::size_t i = 0;
  61. 	std::size_t j = 0;
  62.  
  63. 	for (i = 0; i < S.size(); i++) {
  64. 		if (S[i] == ')')break;
  65. 	}
  66. 	for (j = i; j < S.size(); j++) {
  67. 		if (S[j] == '(')break;
  68. 	}
  69.  
  70. 	if (j == S.size())return false;
  71. 	S[i] = '(';
  72. 	S[j] = ')';
  73. 	return ErasePairOne(S);
  74. }
  75. std::int64_t MakeHoge(std::string S) {
  76.  
  77. 	std::uint64_t C = 0;
  78. 	std::string B = S;
  79. 	bool F = true;
  80.  
  81.  
  82. 	while (ErasePairOne(S));
  83. 	B = S;
  84. 	do {
  85. 		F = false;
  86. 		while (LTurnEraseOneL(S))
  87. 		{
  88. 			C++;
  89. 			B = S;
  90. 		}
  91. 		S = B;
  92. 		while (LTurnEraseOneR(S))
  93. 		{
  94. 			C++;
  95. 			B = S;
  96. 		}
  97. 		S = B;
  98. 		while (RTurnEraseOneL(S))
  99. 		{
  100. 			C++;
  101. 			B = S;
  102. 		}
  103. 		S = B;
  104. 		while (RTurnEraseOneR(S))
  105. 		{
  106. 			C++;
  107. 			B = S;
  108. 		}
  109. 		S = B;
  110. 		while (PairTurnEraseOne(S))
  111. 		{
  112. 			C += 2;
  113. 			B = S;	
  114. 		}
  115. 		S = B;
  116.  
  117. 	} while (S.size()>1);
  118. 	if (S.size() != 0)return -1;
  119.  
  120. 	return C;
  121.  
  122. }
  123.  
  124. /** /
  125. std::int64_t MakeHoge(const std::string& S) {
  126. 	std::string St;
  127. 	std::uint64_t C = 0;
  128. 	for (auto& o : S) {
  129. 		if (o == '(') {
  130. 			St.push_back(o);
  131. 		}
  132. 		if (o == ')') {
  133. 			if (St.size() != 0) {
  134. 				St.pop_back();
  135. 			}
  136. 			else {
  137. 				C++;
  138. 			}
  139.  
  140. 		}		
  141. 	}
  142. 	C += St.size();
  143. 	if (C % 2 == 1) return -1;
  144.  
  145. 	return C/2;
  146.  
  147. }
  148. */
  149. /** /
  150.  
  151. RData countKakko(const std::string& S) {
  152. 	std::uint64_t L = 0;
  153. 	std::uint64_t R = 0;
  154. 	for (auto& o : S) {
  155. 		if (o == '(') L++;
  156. 		if (o == ')')R++;
  157. 	}
  158.  
  159. 	return{ L,R };
  160. }
  161. std::int64_t MakeHoge(const std::string& S) {
  162. 	std::int64_t L = 0;
  163. 	std::int64_t R = 0;
  164. 	std::uint64_t c = 0;
  165. 	std::tie(L, R) = countKakko(S);
  166.  
  167. 	if (L < R) std::swap(L, R);
  168.  
  169. 	while (!(L <= R)) {
  170. 		c++;
  171. 		L--;
  172. 		R++;
  173. 	}
  174.  
  175. 	return L == R ? c : -1;
  176. }
  177. /**/
  178. bool Show(const std::string& S, std::int64_t N) {
  179. 	std::cout << S << " -> " << N << std::endl;
  180. 	return true;
  181. }
  182.  
  183. int main() {
  184. 	std::string S;
  185. 	std::int64_t R = 0;
  186.  
  187. 	S = ")";
  188. 	R = MakeHoge(S);
  189. 	Show(S, R);
  190.  
  191. 	S = "())())";
  192. 	R = MakeHoge(S);
  193. 	Show(S, R);
  194.  
  195. 	S = ")()()(";
  196. 	R = MakeHoge(S);
  197. 	Show(S, R);
  198.  
  199. 	S = ")))(((";
  200. 	R = MakeHoge(S);
  201. 	Show(S, R);
  202.  
  203. 	S = "(())())((())(()(";
  204. 	R = MakeHoge(S);
  205. 	Show(S, R);
  206.  
  207. 	S = "())((())()))()(((()))()((((((((()()(()))";
  208. 	R = MakeHoge(S);
  209. 	Show(S, R);
  210.  
  211. 	return 0;
  212. }
  213.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
) -> -1
())()) -> 1
)()()( -> 2
)))((( -> 4
(())())((())(()( -> 3
())((())()))()(((()))()((((((((()()(())) -> 5
https://ideone.com/OkCwgQ
language:
C++ (gcc 8.3)
created:
6 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!