fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. int x[201];
  6. vector <int> id1;
  7. vector <int> idOdd, idEven;
  8.  
  9. #define MAXN 200001
  10.  
  11. int maxint = ~0U>>1;
  12. int flow;
  13. int pi[MAXN+1], v[MAXN+1];
  14. int S, T;
  15.  
  16. struct etype
  17. {
  18. 	int t, c;
  19. 	etype* next;
  20. 	etype* pair;
  21. 	etype(){next=0;}
  22. 	etype(int _t, int _c, etype* _n){t=_t, c=_c, next=_n;}
  23. }*e[MAXN+1], *eb[MAXN+1], *Pe, *Pool;
  24.  
  25. int aug(int w, int lim)
  26. {
  27. 	int t;
  28. 	v[w] = 1;
  29. 	if(w == T)
  30. 	{
  31. 		flow += lim;
  32. 		return lim;
  33. 	}
  34. 	for(etype *& i=e[w]; i; i = i->next)
  35. 		if(i->c && !v[i->t] && pi[w] == pi[i->t] + 1)
  36. 			if(t = aug(i->t, min(lim, i->c)))
  37. 				return i->c -= t, i->pair->c += t, t;
  38. 	return 0;
  39. }
  40.  
  41. bool fix()
  42. {
  43. 	int t = maxint;
  44. 	for(int i = S; i <= T; i++)
  45. 		if(v[i])
  46. 		{
  47. 			for(etype *j = eb[i]; j; j = j->next)
  48. 				if(j->c && !v[j->t])
  49. 					t = min(t, pi[j->t] + 1 - pi[i]);
  50. 		}
  51. 	if(t == maxint)
  52. 		return 0;
  53.  
  54. 	for(int i = S; i <= T; i++)
  55. 		if(v[i])
  56. 			e[i] = eb[i], pi[i] += t;
  57. 	return 1;
  58. }
  59.  
  60. etype* addedge(int s, int t, int c)
  61. {
  62. 	etype * ret;
  63. 	++Pe;
  64. 	ret = Pe;
  65. 	Pe->t = t, Pe->c = c, Pe->next = e[s];
  66. 	e[s] = Pe;
  67. 	++Pe;
  68. 	Pe->t = s, Pe->c = 0, Pe->next = e[t];
  69. 	e[t] = Pe;
  70. 	e[s]->pair=e[t];
  71. 	e[t]->pair=e[s];
  72. 	return ret;
  73. }
  74.  
  75. void prepare()
  76. {
  77. 	if(Pool == NULL)
  78. 		Pool = new etype[1000001];
  79. 	Pe = Pool;
  80. 	memset(e, 0, sizeof(e));
  81. }
  82.  
  83. int MaxFlow()
  84. {
  85. 	flow = 0;
  86. 	memcpy(eb, e, sizeof(e));
  87. 	memset(pi, 0, sizeof(pi));
  88. 	do
  89. 	{
  90. 		do
  91. 		memset(v, 0, sizeof(v));
  92. 		while(aug(S, maxint));
  93. 	}
  94. 	while(fix());
  95. 	return flow;
  96. }
  97.  
  98. /*  Note
  99. 	1. Set maxNodes here: #define MAXN 200001
  100. 	2. Set maxEdges here: Pool = new etype[1000001];
  101. 	3. S must be the min id, T must be the max id
  102. */
  103.  
  104. /*  Eaxmple
  105. 	prepare();
  106. 	S = 1, T = 2;
  107. 	addedge(1, 2, 3);
  108. 	cout << MaxFlow() << endl;
  109. */
  110.  
  111. int isPrime(int x)
  112. {
  113. 	if(x < 2) return false;
  114. 	for(int i = 2; i * i <= x; i++)
  115. 		if(x % i == 0)
  116. 			return false;
  117. 	return true;
  118. }
  119.  
  120. vector <int> e2[201];
  121. etype *flowEdge[201][201];
  122. bool visited[201];
  123.  
  124. int MAIN()
  125. {
  126. 	cin >> n;
  127. 	int nOdd = 0, nEven = 0;
  128. 	for(int i = 1; i <= n; i++)
  129. 	{
  130. 		cin >> x[i];
  131. 		if(x[i] > 1 && x[i] % 2 == 0)
  132. 		{
  133. 			nEven ++;
  134. 			idEven.push_back(i);
  135. 		}
  136. 		if(x[i] > 1 && x[i] % 2 == 1)
  137. 		{
  138. 			nOdd ++;
  139. 			idOdd.push_back(i);
  140. 		}
  141. 	}
  142. 	int needOne = nEven - nOdd;
  143. 	int oneIn = 0, oneOut = 0;
  144. 	for(int i = 1; i <= n; i++)
  145. 		if(x[i] == 1)
  146. 		{
  147. 			if(needOne > 0)
  148. 			{
  149. 				idOdd.push_back(i);
  150. 				oneIn ++;
  151. 				needOne --;
  152. 			}
  153. 			else
  154. 			{
  155. 				id1.push_back(i);
  156. 				oneOut ++;
  157. 			}
  158. 		}
  159.  
  160. 	if((oneIn == false && (oneOut == 1 || oneOut == 2)) || (idOdd.size() != idEven.size()))
  161. 	{
  162. 		cout << "Impossible" << endl;
  163. 		return 0;
  164. 	}
  165. 	//cout << oneIn << " / " << oneOut << endl;
  166.  
  167. 	int eachSide = idOdd.size();
  168. 	S = 1;
  169. 	T = 2 * (1 + eachSide);
  170. 	prepare();
  171. 	for(int i = 0; i < eachSide; i++)
  172. 		addedge(S, 2 + i, 2);
  173. 	for(int i = 0; i < eachSide; i++)
  174. 		addedge(2 + eachSide + i, T, 2);
  175. 	for(int i = 0; i < eachSide; i++)
  176. 		for(int j = 0; j < eachSide; j++)
  177. 			if(isPrime(x[idOdd[i]] + x[idEven[j]]))
  178. 			{
  179. 				if(x[idOdd[i]] == 1 && oneIn > 0 && oneOut > 0)
  180. 				{
  181. 					flowEdge[i][j] = addedge(2 + i, 2 + eachSide + j, 2);
  182. 				}
  183. 				else
  184. 					flowEdge[i][j] = addedge(2 + i, 2 + eachSide + j, 1);
  185. 				//cout << i << " " << j << " : " << x[idOdd[i]] << " + " << x[idEven[j]] << endl;
  186. 			}
  187. 			else
  188. 				flowEdge[i][j] = NULL;
  189. 	int f = MaxFlow();
  190.  
  191. 	if(f != 2 * eachSide)
  192. 	{
  193. 		cout << "Impossible" << endl;
  194. 	}
  195. 	else
  196. 	{
  197. 		vector< vector <int> > ans, one;
  198. 		if(id1.size() != 0)
  199. 		{
  200. 			if(oneIn > 0)
  201. 				one.push_back(id1);
  202. 			else
  203. 				ans.push_back(id1);
  204. 		}
  205. 		for(int i = 0; i < eachSide; i++)
  206. 			for(int j = 0; j < eachSide; j++)
  207. 				if(flowEdge[i][j] != NULL)
  208. 					if(flowEdge[i][j] -> pair -> c > 0)
  209. 					{
  210. 						int a = idOdd[i];
  211. 						int b = idEven[j];
  212. 						e2[a].push_back(b);
  213. 						e2[b].push_back(a);
  214. 					}
  215. 		memset(visited, false, sizeof(visited));
  216. 		for(int i = 1; i <= n; i++)
  217. 			if(visited[i] == false && e2[i].size() > 0)
  218. 			{
  219. 				vector <int> t;
  220. 				int cur = i;
  221. 				visited[cur] = true;
  222. 				t.push_back(i);
  223. 				while(true)
  224. 				{
  225. 					if(visited[e2[cur][0]] == false)
  226. 						cur = e2[cur][0];
  227. 					else if(e2[cur].size() > 1 && visited[e2[cur][1]] == false)
  228. 						cur = e2[cur][1];
  229. 					else
  230. 						break;
  231. 					t.push_back(cur);
  232. 					visited[cur] = true;
  233.  
  234. 				}
  235. 				int pos1 = -1;
  236. 				for(int j = 0; j < t.size(); j++)
  237. 					if(x[t[j]] == 1)
  238. 						pos1 = j;
  239. 				if(pos1 == -1 || oneIn == false || oneOut == false)
  240. 					ans.push_back(t);
  241. 				else
  242. 				{
  243. 					vector <int> t2;
  244. 					for(int j = pos1; j < t.size(); j++)
  245. 						t2.push_back(t[j]);
  246. 					for(int j = 0; j < pos1; j++)
  247. 						t2.push_back(t[j]);
  248. 					one.push_back(t2);
  249. 				}
  250. 			}
  251.  
  252. 		if(one.size() > 0)
  253. 		{
  254. 			vector <int> t;
  255. 			for(int i = 0; i < one.size(); i++)
  256. 				for(int j = 0; j < one[i].size(); j++)
  257. 					t.push_back(one[i][j]);
  258. 			ans.push_back(t);
  259. 		}
  260. 		cout << ans.size() << endl;
  261. 		for(int i = 0; i < ans.size(); i++)
  262. 		{
  263. 			cout << ans[i].size() << " ";
  264. 			for(int j = 0; j < ans[i].size(); j++)
  265. 			{
  266. 				cout << ans[i][j] << (j == ans[i].size() - 1 ? "\n" : " ");
  267. 			}
  268. 		}
  269. 	}
  270.  
  271. 	return 0;
  272. }
  273.  
  274. int main()
  275. {
  276. 	#ifdef LOCAL_TEST
  277. 		freopen("in.txt", "r", stdin);
  278. 		freopen("out.txt", "w", stdout);
  279. 	#endif
  280. 	ios :: sync_with_stdio(false);
  281. 	cout << fixed << setprecision(16);
  282. 	return MAIN();
  283. }
  284.  
Success #stdin #stdout 0.01s 22200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/z3FsU2
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!