fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.  
  6. 	// #ifndef ONLINE_JUDGE
  7.  //    	freopen("input", "r", stdin);
  8.  //    	freopen("output", "w", stdout);
  9. 	// #endif
  10. 	ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.  
  13.     int n;
  14.     cin>>n;
  15.  
  16.     vector<pair<pair<int,int>,int> > firstRow;
  17.     vector<pair<pair<int,int>,int> > secondRow;
  18.  
  19.     pair<int,int> minipair;
  20.  
  21.     for(int i=0;i<n;i++){
  22.     	cin>>minipair.first;
  23.     	firstRow.push_back(make_pair(minipair, i));
  24.     }
  25.     for(int i=0;i<n;i++){
  26.     	cin>>firstRow[i].first.second;
  27.     }
  28.  
  29.     for(int i=0;i<n;i++){
  30.     	cin>>minipair.first;
  31.     	secondRow.push_back(make_pair(minipair,i));
  32.     }
  33.     for(int i=0;i<n;i++){
  34.     	cin>>secondRow[i].first.second;
  35.     }
  36.  
  37.     sort(firstRow.begin(),firstRow.end());
  38.     sort(secondRow.begin(),secondRow.end());
  39.  
  40. 	int firstRowAnsArr[n];
  41. 	int secondRowAnsArr[n];
  42. 	int tj=0;
  43. 	int tk=0;
  44. 	int bj=0;
  45. 	int bk=0;
  46.  
  47. 	set<pair<int,int> > topset;
  48. 	set<pair<int,int> > botset;
  49. 	pair<int,int> tempPair;
  50.  
  51. 	int myMin;
  52. 	int currVal;
  53. 	int currInd;
  54. 	set<pair<int,int> >::iterator it;
  55.  
  56. 	int bigIter = 0;
  57. 	while(bigIter<n){
  58.  
  59. 		if(topset.empty()){
  60.  
  61. 			// while(tj<n){
  62. 			// 	topset.insert(make_pair(firstRow[tj].first.second, firstRow[tj].second));
  63. 			// 	tj++;
  64. 			// 	if(tj==n || firstRow[tj].first.first  != firstRow[tj-1].first.first) break;
  65. 			// }
  66.  
  67. 			tk = tj+1;
  68. 			while(tk<n && firstRow[tk].first.first == firstRow[tk-1].first.first)tk++;
  69. 			tk--;
  70. 			for(int i=tj;i<=tk;i++){
  71. 				tempPair.first = firstRow[i].first.second;
  72. 				tempPair.second = firstRow[i].second;
  73. 				topset.insert(tempPair);
  74. 			}
  75. 			tj = tk+1;
  76. 		}
  77.  
  78. 		if(botset.empty()){
  79. 			// while(bj<n){
  80. 			// 	botset.insert(make_pair(secondRow[bj].first.second, secondRow[bj].second));
  81. 			// 	bj++;
  82. 			// 	if(bj==n || secondRow[bj].first.first  != secondRow[bj-1].first.first) break;
  83. 			// }
  84.  
  85.  
  86. 			bk = bj+1;
  87. 			while(bk<n && secondRow[bk].first.first == secondRow[bk-1].first.first)bk++;
  88. 			bk--;
  89. 			for(int i=bj;i<=bk;i++){
  90. 				tempPair.first = secondRow[i].first.second;
  91. 				tempPair.second = secondRow[i].second;
  92. 				botset.insert(tempPair);
  93. 			}
  94. 			bj = bk+1;
  95. 		}
  96.  
  97.  
  98. 		myMin = min(botset.size(),topset.size());
  99. //		cout<<bigIter<<" "<<botset.size()<<" "<<topset.size()<<endl;
  100.  
  101. 		if(myMin==0){
  102. 			cout<<"impossible"<<endl;
  103. 			return 0;
  104. 		}
  105.  
  106. 		if(myMin==botset.size()){
  107. 			while(!botset.empty()){
  108. 				currVal = (*botset.begin()).first;
  109. 				currInd = (*botset.begin()).second;
  110. 				botset.erase(botset.begin());
  111. 				it = lower_bound(topset.begin(), topset.end(), make_pair(currVal+1,-1));
  112. 				if(it==topset.end()){
  113. 					cout<<"impossible"<<endl;
  114. 					return 0;
  115. 				}
  116. 				else{
  117. 					firstRowAnsArr[bigIter] = (*it).second;
  118. 					secondRowAnsArr[bigIter] = currInd;
  119. 					topset.erase(it);
  120. 				}
  121. 				bigIter++;
  122. 			}
  123. 		}
  124. 		else{
  125. 			while(!topset.empty()){
  126. 				currVal = (*topset.begin()).first;
  127. 				currInd = (*topset.begin()).second;
  128. 				topset.erase(topset.begin());
  129. 				it = lower_bound(botset.begin(), botset.end(), make_pair(currVal-1,INT_MAX));
  130. 				if(it==botset.begin()){
  131. 					cout<<"impossible"<<endl;
  132. 					return 0;
  133. 				}
  134. 				else{
  135. 					it--;
  136. 					firstRowAnsArr[bigIter] = currInd;
  137. 					secondRowAnsArr[bigIter] = (*it).second;
  138. 					botset.erase(it);
  139. 				}
  140. 				bigIter++;
  141. 			}
  142. 		}
  143. 	}
  144.  
  145. 	for(int i=0;i<n;i++){
  146. 		cout<<firstRowAnsArr[i]+1<<" ";
  147. 	}
  148. 	cout<<endl;
  149. 	for(int i=0;i<n;i++){
  150. 		cout<<secondRowAnsArr[i]+1<<" ";
  151. 	}
  152. 	cout<<endl;
  153. 	return 0;
  154. }
  155.  
Success #stdin #stdout 0s 15376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
impossible
https://ideone.com/UAN7JK
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!