fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int n, m;
  8. int k, logk;
  9.  
  10.  
  11. int fuck;
  12.  
  13.  
  14.  
  15. int main(){
  16. 	cin>>n;
  17. 	k=1;
  18. 	logk=1;
  19. 	while(k<n){
  20. 		k*=2;
  21. 		logk++;
  22. 	}
  23.  
  24. 	vector< pair<int,int> > tree[2*k-1];
  25.  
  26. 	int a,b;
  27. 	for(int i=2*k-2; i>(2*k-2-(n-k)); i--){
  28. 		tree[i].push_back(make_pair(0,0));
  29. 	}
  30.  
  31. 	for(int i=k-1; i<=(2*k-2+(n-k)); i++){
  32.  
  33. 		cin>>a;
  34. 		cin>>b;
  35. 		if(a==b){
  36. 			tree[i].push_back(make_pair(a,a));
  37. 		}
  38. 		else{
  39. 			tree[i].push_back(make_pair(min(a,b),max(a,b)));
  40. 			tree[i].push_back(make_pair(a,a));
  41. 			tree[i].push_back(make_pair(b,b));
  42. 		}
  43. 	}
  44.  
  45. 	for(int i=k-2; i>=0; i--){
  46. 		//Bierzemy pod uwagę węzły o numerach 2*i+1 oraz 2*i+2
  47. 		for(pair<int,int> t : tree[2*i+1]){
  48. 			for(pair<int,int> s : tree[2*i+2]){
  49. 				if(t.second<=s.first){
  50. 					tree[i].push_back(make_pair(t.first,s.second));
  51. 				}
  52. 			}
  53. 		}
  54.  
  55. 		//Redukcja elementów w tree[i]
  56. 		for (int j = 0; j < tree[i].size(); j++)
  57. 		{
  58.  
  59. 			for (int q = j+1; q < tree[i].size(); q++)
  60. 			{
  61. 				if((tree[i][j].first==tree[i][q].first) and (tree[i][j].second==tree[i][q].second)){
  62. 					tree[i].erase(tree[i].begin()+q);
  63. 					q--;
  64. 				}
  65. 			}
  66. 		}
  67. 	} 
  68.  
  69. 	/*
  70. 4
  71. 2 5
  72. 3 4
  73. 6 3
  74. 2 7
  75. 2
  76. 3 4
  77. 1 3
  78.  
  79.  
  80.  
  81. 	4 5
  82. 	1 3
  83. 	2 4
  84. 	1 5
  85. 	5 6
  86. 	*/
  87.  
  88. 	/*while(true){
  89. 		cin>>a;
  90. 		if(tree[a].size()){
  91. 			cout<<tree[a][0].first<<':'<<tree[a][0].second<<endl;
  92. 		}
  93. 		else{
  94. 			cout<<"Empty"<<endl;
  95. 		}
  96. 	}*/
  97.  
  98. 	//Teraz zaczyna się zabawa - zmieniamy 2 kolejne karty
  99. 	pair <int,int> robocze1, robocze2;
  100. //cout<<endl<<'a'<<endl;
  101. 	cin>>m;
  102.  
  103. 	int swap1[m], swap2[m];
  104. 	for (int i = 0; i < m; i++)
  105. 	{
  106. 		cin>>swap1[i];
  107.  
  108. 		cin>>swap2[i];
  109. 	}
  110.  
  111. 	cout<<endl<<swap2[1];
  112.  
  113. 	for (int id = 0; id < m; id++)
  114. 	{
  115. 		cout<<id;
  116. 		int c = 3;
  117. 		swap1[id]=swap1[id]+c;
  118. 		swap2[id]=swap2[id]+c;
  119. 		robocze1=tree[swap1[id]][0];
  120. 		robocze2=tree[swap2[id]][0];
  121. 		tree[swap1[id]].clear();
  122. 		tree[swap2[id]].clear();
  123. 		tree[swap1[id]].push_back(robocze2);
  124. 		tree[swap2[id]].push_back(robocze1);
  125.  
  126. 		for (int i = 1; i < logk; i++)
  127. 		{
  128. 			swap1[id]=(swap1[id]-1)/2;
  129. 			swap2[id]=(swap2[id]-1)/2;
  130. 			if(swap1[id]!=swap2[id]){
  131. 				//Zmiana w swap1[id]
  132. 				for(pair<int,int> t :tree[2*swap1[id]+1]){
  133. 					for(pair<int,int> s :tree[2*swap1[id]+2]){
  134. 						if(t.second<=s.first){
  135. 							tree[i].push_back(make_pair(t.first,s.second));
  136. 						}
  137. 					}
  138. 				}
  139.  
  140. 				//Redukcja elementów w tree[i]
  141. 				for (int j = 0; j < tree[swap1[id]].size(); j++)
  142. 				{
  143.  
  144. 					for (int q = j+1; q < tree[swap1[id]].size(); q++)
  145. 					{
  146. 						if((tree[swap1[id]][j].first==tree[swap1[id]][q].first) and (tree[swap1[id]][j].second==tree[swap1[id]][q].second)){
  147. 							tree[swap1[id]].erase(tree[swap1[id]].begin()+q);
  148. 							q--;
  149. 						}
  150. 					}
  151. 				}
  152.  
  153. 				//Zmiana w d
  154. 				for(pair<int,int> t :tree[2*swap2[id]+1]){
  155. 					for(pair<int,int> s :tree[2*swap2[id]+2]){
  156. 						if(t.second<=s.first){
  157. 							tree[i].push_back(make_pair(t.first,s.second));
  158. 						}
  159. 					}
  160. 				}
  161.  
  162. 				//Redukcja elementów w tree[i]
  163. 				for (int j = 0; j < tree[swap2[id]].size(); j++)
  164. 				{
  165.  
  166. 					for (int q = j+1; q < tree[swap2[id]].size(); q++)
  167. 					{
  168. 						if((tree[swap2[id]][j].first==tree[swap2[id]][q].first) and (tree[swap2[id]][j].second==tree[swap2[id]][q].second)){
  169. 							tree[swap2[id]].erase(tree[swap2[id]].begin()+q);
  170. 							q--;
  171. 						}
  172. 					}
  173. 				}
  174. 			}
  175. 		}
  176.  
  177. 		if(tree[0].size()>0){
  178. 			cout<<"TAK"<<endl;
  179. 		}
  180. 		else{
  181. 			cout<<"NIE"<<endl;
  182. 		}
  183. 	}
  184.  
  185. 	return 0;
  186. }
Runtime error #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
4
2 5
3 4
6 3
2 7
2
3 4
1 3
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/HfhP7x
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
4 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!