fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 10e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. #define maxL 150000
  24. // mylittlepony
  25. using namespace std;
  26.  
  27. pair<string,string> makeR(int seed) {
  28. 	srand(seed);
  29. 	int N =rand()%maxL+1, M =rand()%maxL+1;
  30. 	pair<string,string> ret;
  31. 	char c[] ="URL12";
  32. 	int d =0;
  33. 	for(int i =0; i < N; i++) {
  34. 		int x =rand()%5;
  35. 		while(x == 0 && d == 0) x =rand()%5;
  36. 		while(d == 0 && x <= 2) x =rand()%5;
  37. 		if(x > 2) d++;
  38. 		if(x == 0) d--;
  39. 		ret.ff +=c[x];}
  40. 	d =0;
  41. 	for(int i =0; i < M; i++) {
  42. 		int x =rand()%5;
  43. 		while(x == 0 && d == 0) x =rand()%5;
  44. 		while(d == 0 && x <= 2) x =rand()%5;
  45. 		if(x > 2) d++;
  46. 		if(x == 0) d--;
  47. 		ret.ss +=c[x];}
  48. 	return ret;}
  49.  
  50. int bruteforce(string s, string t) {
  51. 	vector< vector<int> > G(5000);
  52. 	for(int i =1; i <= 2000; i++) {
  53. 		G[2*i+1].push_back(i);
  54. 		G[2*i].push_back(i);
  55. 		G[i].push_back(2*i);
  56. 		G[i].push_back(2*i+1);
  57. 		int a =i+1;
  58. 		while(a%2 == 0) a /=2;
  59. 		if(a != 1) {
  60. 			G[i].push_back(i+1);
  61. 			G[i+1].push_back(i);}}
  62. 	int a =1, b =1;
  63. 	for(int i =0; i < s.length(); i++) {
  64. 		if(s[i] == 'U') a /=2;
  65. 		if(s[i] == '1') a =2*a;
  66. 		if(s[i] == '2') a =2*a+1;
  67. 		if(s[i] == 'L') a--;
  68. 		if(s[i] == 'R') a++;}
  69. 	for(int i =0; i < t.length(); i++) {
  70. 		if(t[i] == 'U') b /=2;
  71. 		if(t[i] == '1') b =2*b;
  72. 		if(t[i] == '2') b =2*b+1;
  73. 		if(t[i] == 'L') b--;
  74. 		if(t[i] == 'R') b++;}
  75. 	queue<int> q; q.push(a);
  76. 	if(a < 0 || b < 0) return -1;
  77. 	vector<int> dist(5000,1000000);
  78. 	dist[a] =0;
  79. 	while(!q.empty()) {
  80. 		for(int i =0; i < G[q.front()].size(); i++) if(dist[G[q.front()][i]] > dist[q.front()]+1) {
  81. 			dist[G[q.front()][i]] =dist[q.front()]+1;
  82. 			q.push(G[q.front()][i]);}
  83. 		q.pop();}
  84. 	return dist[b];}
  85.  
  86. int solve(string s, string t) {
  87. 	// do pekneho tvaru
  88. 	stack< pair<int,int> > A;
  89. 	stack< pair<int,int> > B;
  90. 	int dA =0, dB =0;
  91. 	for(int i =0; i < s.length(); i++) {
  92. 		if(s[i] == 'U') {
  93. 			dA--;
  94. 			if(A.empty()) return -1; 
  95. 			pair<int,int> p =A.top(); A.pop();
  96. 			p.ss--;
  97. 			if(p.ss > 0) A.push(p);}
  98. 		if(s[i] == '1') { dA++;
  99. 			if(A.empty() || A.top().ff == 1) {A.push(make_pair(0,1)); continue;}
  100. 			pair<int,int> p =A.top(); A.pop();
  101. 			p.ss++;
  102. 			A.push(p);}
  103. 		if(s[i] == '2') { dA++;
  104. 			if(A.empty() || A.top().ff == 0) {A.push(make_pair(1,1)); continue;}
  105. 			pair<int,int> p =A.top(); A.pop();
  106. 			p.ss++;
  107. 			A.push(p);}
  108. 		if(s[i] == 'R') {
  109. 			if(A.empty()) return -1; 
  110. 			pair<int,int> p =A.top(); A.pop();
  111. 			if(p.ff == 0) {
  112. 				p.ss--; if(p.ss > 0) {A.push(p);
  113. 				A.push(make_pair(1,1));}
  114. 				else {
  115. 					if(A.empty()) A.push(make_pair(1,1));
  116. 					else A.top().ss++;}
  117. 				continue;}
  118. 			if(A.empty()) return -1; 
  119. 			p.ff =0;
  120. 			pair<int,int> r =A.top(); A.pop();
  121. 			r.ss--;
  122. 			if(r.ss > 0) {
  123. 				A.push(r); 
  124. 				A.push(make_pair(1,1));
  125. 				A.push(p);
  126. 				continue;}
  127. 			if(!A.empty()) A.top().ss++;
  128. 			else A.push(make_pair(1,1));
  129. 			A.push(p);}
  130. 		if(s[i] == 'L') {
  131. 			if(A.empty()) return -1; 
  132. 			pair<int,int> p =A.top(); A.pop();
  133. 			if(p.ff == 1) {
  134. 				p.ss--; if(p.ss > 0) {A.push(p);
  135. 				A.push(make_pair(0,1));}
  136. 				else {
  137. 					if(A.empty()) A.push(make_pair(0,1));
  138. 					else A.top().ss++;}
  139. 				continue;}
  140. 			if(A.empty()) return -1;
  141. 			p.ff =1;
  142. 			pair<int,int> r =A.top(); A.pop();
  143. 			r.ss--;
  144. 			if(r.ss > 0) {
  145. 				A.push(r); 
  146. 				A.push(make_pair(0,1));
  147. 				A.push(p);
  148. 				continue;}
  149. 			if(!A.empty()) A.top().ss++;
  150. 			else A.push(make_pair(0,1));
  151. 			A.push(p);}}
  152. 	for(int i =0; i < t.length(); i++) {
  153. 		if(t[i] == 'U') { dB--;
  154. 			if(B.empty()) return -1; 
  155. 			pair<int,int> p =B.top(); B.pop();
  156. 			p.ss--;
  157. 			if(p.ss > 0) B.push(p);}
  158. 		if(t[i] == '1') { dB++;
  159. 			if(B.empty() || B.top().ff == 1) {B.push(make_pair(0,1)); continue;}
  160. 			pair<int,int> p =B.top(); B.pop();
  161. 			p.ss++;
  162. 			B.push(p);}
  163. 		if(t[i] == '2') { dB++;
  164. 			if(B.empty() || B.top().ff == 0) {B.push(make_pair(1,1)); continue;}
  165. 			pair<int,int> p =B.top(); B.pop();
  166. 			p.ss++;
  167. 			B.push(p);}
  168. 		if(t[i] == 'R') {
  169. 			if(B.empty()) return -1; 
  170. 			pair<int,int> p =B.top(); B.pop();
  171. 			if(p.ff == 0) {
  172. 				p.ss--; if(p.ss > 0) {B.push(p);
  173. 				B.push(make_pair(1,1));}
  174. 				else {
  175. 					if(B.empty()) B.push(make_pair(1,1));
  176. 					else B.top().ss++;}
  177. 				continue;}
  178. 			if(B.empty()) return -1; 
  179. 			p.ff =0;
  180. 			pair<int,int> r =B.top(); B.pop();
  181. 			r.ss--;
  182. 			if(r.ss > 0) {
  183. 				B.push(r); 
  184. 				B.push(make_pair(1,1));
  185. 				B.push(p);
  186. 				continue;}
  187. 			if(!B.empty()) B.top().ss++;
  188. 			else B.push(make_pair(1,1));
  189. 			B.push(p);}
  190. 		if(t[i] == 'L') {
  191. 			if(B.empty()) return -1; 
  192. 			pair<int,int> p =B.top(); B.pop();
  193. 			if(p.ff == 1) {
  194. 				p.ss--; if(p.ss > 0) {B.push(p);
  195. 				B.push(make_pair(0,1));}
  196. 				else {
  197. 					if(B.empty()) B.push(make_pair(0,1));
  198. 					else B.top().ss++;}
  199. 				continue;}
  200. 			if(B.empty()) return -1; 
  201. 			p.ff =1;
  202. 			pair<int,int> r =B.top(); B.pop();
  203. 			r.ss--;
  204. 			if(r.ss > 0) {
  205. 				B.push(r); 
  206. 				B.push(make_pair(0,1));
  207. 				B.push(p);
  208. 				continue;}
  209. 			if(!B.empty()) B.top().ss++;
  210. 			else B.push(make_pair(0,1));
  211. 			B.push(p);}}
  212.  
  213. 	if(dA > dB) {swap(A,B); swap(dA,dB);}
  214. 	int D =0, ans =100000;
  215. 	while(dA < dB) {
  216. 		D++, dB--;
  217. 		pair<int,int> p =B.top(); B.pop();
  218. 		p.ss--; if(p.ss > 0) B.push(p);}
  219.  
  220. 	vector<int> Va,Vb;
  221. 	while(!A.empty()) {
  222. 		pair<int,int> p =A.top(); A.pop();
  223. 		for(int i =0; i < p.ss; i++) Va.push_back(p.ff);}
  224. 	while(!B.empty()) {
  225. 		pair<int,int> p =B.top(); B.pop();
  226. 		for(int i =0; i < p.ss; i++) Vb.push_back(p.ff);}
  227. /*	ALL_THE(Va,it) cout << *it;
  228. 	cout << ".\n";
  229. 	ALL_THE(Vb,it) cout << *it;
  230. 	cout << ".\n";
  231. */	
  232. 	int d =0;
  233. 	ans =2*Va.size();
  234. 	for(int i =0; i < Va.size(); i++) {
  235. 		d =2*d+Va[Va.size()-1-i]-Vb[Vb.size()-1-i];
  236. 		if(abs(d) > 100000000) break;
  237. 		ans =min(ans,2*((int)Va.size()-1-i)+abs(d));}
  238. 	return ans+D;}
  239.  
  240. int main() {
  241.     cin.sync_with_stdio(0);
  242.     srand(time(0));
  243.     string s,t;
  244.     cin >> s >> t;
  245. //    cout << bruteforce(s,t) << "\n";
  246.     cout << solve(s,t) << "\n";
  247. /*    for(int i =0; i < 100; i++) {
  248.     	pair<string,string> s =makeR(rand()%10000000);
  249. //    	if(bruteforce(s.ff,s.ss) != solve(s.ff,s.ss) && solve(s.ff,s.ss) != -1) 
  250. //    		cout << s.ff << " " << s.ss << endl;
  251.     	if(solve(s.ff,s.ss) != -1) cout << "." << endl;}
  252. */    return 0;}
  253.  
  254. // look at my code
  255. // my code is amazing
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
2111111111111
1222222222222
stdout
copy 
1
https://ideone.com/b9BVnR
ceoi 2013 d2
language:
C++14 (gcc 8.3)
created:
11 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!