fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. vector <int> e[1001];
  6. bool have[1001];
  7.  
  8. struct node
  9. {
  10. 	int leftMark, rightMark;
  11. 	node* sonLeft, *sonRight;
  12. 	void updateMark()
  13. 	{
  14. 		leftMark = sonLeft->leftMark;
  15. 		rightMark = sonRight->rightMark;
  16. 	}
  17. }*start, *want;
  18.  
  19. struct step
  20. {
  21. 	int fromA, fromB;
  22. 	int toA, toB;
  23. };
  24.  
  25. node* addNode(int L, int R, int from)
  26. {
  27. 	node *t = new node();
  28. 	t->leftMark = L;
  29. 	t->rightMark = R;
  30. 	if(L == R+1)
  31. 	{
  32. 		return t;
  33. 	}
  34. 	for(int i = 0; i < e[L].size(); i++)
  35. 		if(e[L][i] != from)
  36. 			have[e[L][i]] = true;
  37. 	int M = -1;
  38. 	for(int j = 0; j < e[R].size(); j++)
  39. 		if(e[R][j] != from)
  40. 			if(have[e[R][j]])
  41. 				M = e[R][j];
  42. 	for(int i = 0; i < e[L].size(); i++)
  43. 		have[e[L][i]] = false;
  44. 	t->sonLeft = addNode(L, M, R);
  45. 	t->sonRight = addNode(M, R, L);
  46. 	return t;
  47. }
  48.  
  49. node* input()
  50. {
  51. 	for(int i = 1; i <= n; i++)
  52. 		e[i].clear();
  53. 	for(int i = 1; i <= n-3; i++)
  54. 	{
  55. 		int a, b;
  56. 		cin >> a >> b;
  57. 		e[a].push_back(b);
  58. 		e[b].push_back(a);
  59. 	}
  60. 	for(int i = 1; i <= n; i++)
  61. 	{
  62. 		int j = i+1;
  63. 		if(i == n) j = 1;
  64. 		e[i].push_back(j);
  65. 		e[j].push_back(i);
  66. 	}
  67. 	return addNode(n, 1, -1);
  68. }
  69.  
  70. void print(node *p, string append)
  71. {
  72. 	cout << append << p->leftMark << " " << p->rightMark << endl;
  73. 	if(p->sonLeft != NULL)
  74. 		print(p->sonLeft, append + "\t");
  75. 	if(p->sonRight != NULL)
  76. 		print(p->sonRight, append + "\t");
  77. }
  78.  
  79. vector <step> record;
  80.  
  81. void rotateToRight(node *r)
  82. {
  83. 	step t;
  84. 	node *s = r->sonLeft;
  85. 	node *a = s->sonLeft;
  86. 	node *b = s->sonRight;
  87. 	node *c = r->sonRight;
  88. 	t.fromA = s->leftMark;
  89. 	t.fromB = s->rightMark;
  90. 	r->sonLeft = a;
  91. 	r->sonRight = s;
  92. 	s->sonLeft = b;
  93. 	s->sonRight = c;
  94. 	s->updateMark();
  95. 	r->updateMark();
  96. 	t.toA = s->leftMark;
  97. 	t.toB = s->rightMark;
  98. 	record.push_back(t);
  99. }
  100.  
  101. void rotateToLeft(node *r)
  102. {
  103. 	step t;
  104. 	node *s = r->sonRight;
  105. 	node *a = r->sonLeft;
  106. 	node *b = s->sonLeft;
  107. 	node *c = s->sonRight;
  108. 	t.fromA = s->leftMark;
  109. 	t.fromB = s->rightMark;
  110. 	r->sonLeft = s;
  111. 	r->sonRight = c;
  112. 	s->sonLeft = a;
  113. 	s->sonRight = b;
  114. 	s->updateMark();
  115. 	r->updateMark();
  116. 	t.toA = s->leftMark;
  117. 	t.toB = s->rightMark;
  118. 	record.push_back(t);
  119. }
  120.  
  121. void rotateMiddleToRoot(node *p, int middle)
  122. {
  123. 	int myMiddle = p->sonLeft->rightMark;
  124. 	if(myMiddle == middle)
  125. 		return;
  126. 	if(myMiddle < middle)
  127. 	{
  128. 		rotateMiddleToRoot(p->sonLeft, middle);
  129. 		rotateToRight(p);
  130. 	}
  131. 	else if(myMiddle > middle)
  132. 	{
  133. 		rotateMiddleToRoot(p->sonRight, middle);
  134. 		rotateToLeft(p);
  135. 	}
  136. }
  137.  
  138. void normalize(node *p)
  139. {
  140. 	if(p->leftMark - p->rightMark <= 2) return;
  141. 	int middle = (p->leftMark + p->rightMark) / 2;
  142. 	rotateMiddleToRoot(p, middle);
  143. 	normalize(p->sonLeft);
  144. 	normalize(p->sonRight);
  145. }
  146.  
  147. int MAIN()
  148. {
  149. 	memset(have, 0, sizeof(have));
  150. 	cin >> n;
  151. 	start = input();
  152. 	normalize(start);
  153. 	vector <step> record1 = record;
  154. 	record.clear();
  155. 	want = input();
  156. 	normalize(want);
  157.  
  158. 	cout << record.size() + record1.size() << endl;
  159.  
  160. 	for(int i = 0; i < record1.size(); i++)
  161. 		cout << record1[i].fromA << " " << record1[i].fromB << endl;
  162. 	for(int i = record.size()-1; i >= 0; i--)
  163. 		cout << record[i].toA << " " << record[i].toB << endl;
  164. 	return 0;
  165. }
  166.  
  167. int main()
  168. {
  169. 	#ifdef LOCAL_TEST
  170. 		freopen("in.txt", "r", stdin);
  171. 		freopen("out.txt", "w", stdout);
  172. 	#endif
  173. 	ios :: sync_with_stdio(false);
  174. 	cout << fixed << setprecision(16);
  175. 	return MAIN();
  176. }
  177.  
Runtime error #stdin #stdout 0.01s 14528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Orbacp
language:
C++14 (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!