fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string.h>
  6. #include <math.h>
  7. #include <climits>
  8. #include <stdlib.h>
  9. #include <map>
  10. #include <set>
  11. #include <queue>
  12. #include <string>
  13.  
  14. #define MAXA 10000000
  15. #define MOD 1000000007
  16.  
  17. using namespace std;
  18. typedef set<int> SET;
  19. typedef vector<int> list;
  20. typedef multiset<int> MSET;
  21.  
  22.  
  23. typedef int keyType ;
  24.  
  25. map <int, SET> keyMap;
  26. list ans;
  27. int n;
  28. int debug = 0;
  29.  
  30. char arr[MAXA],*ptr;
  31. long long ret;
  32. inline long long get_int()
  33. {
  34.     ret =0;
  35.     while ( !(*ptr >= '0' && *ptr <= '9'))
  36.         ptr++;
  37.     while (*ptr >= '0' && *ptr<= '9') {
  38.         ret = ret*10 + (*ptr - '0');
  39.         ptr++;
  40.     }
  41.     return ret;
  42. }
  43.  
  44. struct treasure{
  45.     int type;
  46. 	int k;
  47. 	list key;
  48. 	int label;
  49. }chests[205],me;
  50.  
  51. void swapAns(list l){
  52. 	if(ans.size() == 0)
  53. 	{
  54. 		ans = l;
  55. if(debug)		cout << "ANS SIZE WAS 0" << endl;
  56. 	}
  57. 	else {
  58. 		for(int xx =0;xx<n;xx++)
  59. 		{
  60. 			if(l[xx] < ans[xx])
  61. 			{
  62. 				ans = l;
  63. if(debug)				cout << "ANSWER SWAPPED at #:" << xx << "ans=" << ans[xx] << " l=" << l[xx] << endl;
  64. 				return;
  65. 			}
  66. 			if(l[xx] > ans[xx])
  67. 				return;
  68. 		}
  69. 	}
  70. }
  71.  
  72. bool anyUse(list l){
  73. 	if(ans.size() == 0)
  74. 		return true;
  75. 	for(int xx =0;xx<l.size();xx++)
  76. 	{
  77. 		if(l[xx] > ans[xx])
  78. 			return false;
  79. 		if(l[xx] < ans[xx])
  80. 			return true;
  81. 	}
  82. 	return true;
  83. }
  84.  
  85. list traverse(list keys, int opened, SET visited, list orderVisited){
  86.  
  87. 	vector<int> ::iterator it_v;
  88. 	vector<int> ::iterator it_v2;
  89. 	map <int, SET> ::iterator it_m;
  90. 	multiset <int> ::iterator it_s;
  91. 	set <int> ::iterator it_ss;
  92.  
  93. if(debug)	cout << endl;
  94. if(debug)	cout << "OPENED :" << opened << endl;
  95. if(debug)	cout << "KEYS :" ;
  96. if(debug)	for(it_v2 = keys.begin();it_v2 != keys.end();it_v2++)
  97. 		cout << *it_v2 << " ";
  98. if(debug)	cout << endl;
  99.  
  100. if(debug)	cout << "ORDERED VISITED CHESTS :" ;
  101. if(debug)	for(it_v2 = orderVisited.begin();it_v2 != orderVisited.end();it_v2++)
  102. 		cout << *it_v2 << " ";
  103. if(debug)	cout << endl << endl;
  104.  
  105. 	if(opened == n)
  106. 		return orderVisited;
  107. 	if(keys.size() == 0)
  108. 		return orderVisited;
  109.  
  110. 	if(!anyUse(orderVisited))
  111. 		return orderVisited;
  112.  
  113. 	for(it_v = keys.begin();it_v != keys.end();it_v++)
  114. 	{
  115. 		int key = *it_v;
  116. 		it_m = keyMap.find(key);
  117. 		if(it_m != keyMap.end()){
  118. 			it_s = it_m->second.begin();
  119. 			while(it_s != it_m->second.end()){
  120. 				int chest = *it_s;
  121. 				it_s++;
  122. 				it_ss = visited.find(chest);
  123. 				if( it_ss  == visited.end())
  124. 				{
  125. if(debug)					cout << "KEY USED :" << key << " TO VISIT chest #" << chest << endl;
  126. 					bool flag = false;
  127.  
  128. 					list tlist2 = orderVisited;
  129. 					list tlist;
  130. 					for(it_v2 = keys.begin();it_v2 != keys.end();it_v2++)
  131. 					{
  132. 						if(*it_v2 != key || flag)
  133. 						{
  134. 							tlist.push_back(*it_v2);
  135. 						}
  136. 						if(*it_v2 == key)
  137. 							flag = true;
  138.  
  139. 					}
  140.  
  141. 					for(int xx =0;xx<chests[chest].k;xx++)
  142. 						tlist.push_back(chests[chest].key[xx]);
  143.  
  144. if(debug)					cout << "KEYS WITH ME BEFORE I GO :";
  145. if(debug)					for(it_v2 = tlist.begin();it_v2 != tlist.end();it_v2++)
  146. 						cout << *it_v2 << " ";
  147. if(debug)					cout << endl;
  148.  
  149. 					SET tset = visited;
  150. 					tset.insert(chest);
  151. 					tlist2.push_back(chest);
  152. 					tlist = traverse(tlist, opened+1, tset, tlist2 );
  153. 					if(tlist.size() == n)
  154. 						swapAns(tlist);
  155. 				}
  156.  
  157. 			}
  158. 		}
  159. 	}
  160. 	return orderVisited;
  161. }
  162.  
  163. int main()
  164. {
  165. 	map <int, SET> ::iterator it;
  166.     fread(arr,sizeof(char),MAXA,stdin);
  167.     ptr = arr;
  168. 	int t = get_int();
  169. if(debug)	cout << "T: " << t << endl;
  170. 	int k;
  171. 	for(int tt = 1; tt <= t; tt++)
  172. 	{
  173. 		ans.clear();
  174. 		keyMap.clear();
  175. 		me.k = get_int();
  176. 		n = get_int();
  177. 		me.key.clear();
  178. 		for(int xx =0;xx<n;xx++)
  179. 			chests[xx].key.clear();
  180.  
  181. if(debug)		cout << "MY Key Count : " << me.k << " N: " << n << endl;
  182. 		for(int xx =0;xx<me.k;xx++)
  183. 			me.key.push_back(get_int());
  184.  
  185. 		for(int xx =0;xx<n;xx++)
  186. 		{
  187. 			chests[xx].type = get_int();
  188. 			chests[xx].k = get_int();
  189. 			chests[xx].label = 0;
  190.  
  191. if(debug)			cout << "TYPE :" << chests[xx].type << " KEY COUNT :" << chests[xx].k << endl;
  192. 			for(int yy =0;yy<chests[xx].k;yy++)
  193. 				chests[xx].key.push_back(get_int());
  194.  
  195. if(debug)			cout << "KEYS :";
  196. if(debug)			for(int yy =0;yy<chests[xx].k;yy++)
  197. 						cout << chests[xx].key[yy] << " ";
  198. if(debug)			cout << endl;
  199.  
  200. 			it = keyMap.find(chests[xx].type);
  201. 			if(it == keyMap.end())
  202. 			{
  203. 				SET temp;
  204. 				temp.insert(xx);
  205. 				keyMap[chests[xx].type] = temp;
  206. 			}
  207. 			else
  208. 				(it->second).insert(xx);
  209. 		}
  210. 		SET visited;
  211. 		list tempo;
  212. if(debug)		cout << "\n";
  213. 		tempo = traverse(me.key, 0, visited, tempo);
  214.  
  215.  
  216. 		cout << "Case #" << tt << ": ";
  217. 		if(ans.size() == n)
  218. 		{
  219. 			for(int xx =0;xx<n;xx++)
  220. 				cout << ans[xx]+1 << " ";
  221. 			cout << endl;
  222. 		}
  223. 		else
  224. 			cout << "IMPOSSIBLE" << endl;
  225.  
  226. 	}
  227. 	return 0;
  228.  
  229. }
Success #stdin #stdout 9.5s 12816KB
comments (?)
stdin
copy 
6
1 4
1
1 0
1 2 1 3
2 0
3 1 2
3 3
1 1 1
1 0
1 0
1 0
1 1
2
1 1 1
2 6
1 1
1 1 3
2 0
3 1 2
1 1 5
5 1 6
6 0
3 7
1 2 3
1 2 2 7
2 1 6
3 1 4
4 1 5
5 2 3 7
6 1 5
7 1 2
2 20
1 5
1 1 1
3 1 1
5 2 5 3
1 1 2
1 3 1 2 2
2 1 3
3 4 4 5 1 1
3 1 3
1 1 1
3 1 1
5 2 5 3
1 1 2
1 3 1 2 2
2 1 3
3 4 4 5 1 1
3 1 3
3 5 1 2 3 4 7
7 5 1 2 3 4 8
1 5 1 1 2 2 3
7 5 7 7 1 2 6
stdout
copy 
Case #1: 2 1 4 3 
Case #2: 1 2 3 
Case #3: IMPOSSIBLE
Case #4: 1 3 2 4 5 6 
Case #5: 1 2 3 4 5 6 7 
Case #6: 1 3 2 4 5 6 7 9 11 8 10 12 13 14 15 19 16 17 20 18
https://ideone.com/MxGogf
language:
C++ (gcc 8.3)
created:
12 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!