fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-11-21 09:20:30
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-11-21 12:44:35
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define lb long double
  19. #define ll long long 
  20. #define ull unsigned long long
  21. #define sz(x) x.size()
  22. #define sqr(x) (1LL * (x) * (x))
  23. #define all(x) x.begin(), x.end()
  24. #define fill(f,x) memset(f,x,sizeof(f))
  25. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  26. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  27. #define debug(x) cout << #x << " = " << x << '\n'
  28. #define ii pair<int,int>
  29. #define iii pair<int,ii>
  30. #define di pair<ii,ii>
  31. #define vi vector<int>
  32. #define vii vector<ii>
  33. #define mii map<int,int>
  34. #define fi first
  35. #define se second
  36. #define pb push_back
  37. #define MOD 1000000007
  38. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  39. #define YES cout << "YES\n"
  40. #define NO cout << "NO\n"
  41. #define MASK(i) (1LL << (i))
  42. #define c_bit(i) __builtin_popcountll(i)
  43. #define BIT(x,i) ((x) & MASK(i))
  44. #define SET_ON(x,i) ((x) | MASK(i))
  45. #define SET_OFF(x,i) ((x) & ~MASK(i))
  46. #define oo 1e18
  47. #define name ""
  48. #define endl '\n'
  49. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  50. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  51. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  52. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  53. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  54. const int N = 410;
  55. int n;
  56. ii black[N],white[N];
  57.  
  58. istream& operator>>(istream &in, ii &p) {
  59. 	return in >> p.fi >> p.se;
  60. }
  61.  
  62. namespace sub1 {
  63.  
  64. 	pair<ii,ii> Line[N];
  65.  
  66. 	bool approved() {
  67. 		return n <= 9;
  68. 	}
  69.  
  70. 	int ccw(ii a, ii b, ii c)
  71. 	{
  72. 		int val = (a.fi-b.fi)*(c.se-b.se)-(c.fi-b.fi)*(a.se-b.se);
  73. 		return (val >= 0 ? val ? 1 : 0 : -1);
  74. 	}
  75.  
  76. 	bool check(int a, int b, int c, int d)
  77. 	{
  78. 		if (a > b) swap(a,b);
  79. 		if (c > d) swap(c,d);
  80. 		return (max(a,c) <= min(b,d));
  81. 	}
  82.  
  83. 	bool calc(ii a, ii b, ii c, ii d)
  84. 	{
  85. 		if (!ccw(a,b,c) and !ccw(a,b,d)) return (check(a.fi,b.fi,c.fi,d.fi) and check(a.se,b.se,c.se,d.se));
  86. 		return (ccw(a,c,d) != ccw(b,c,d) and ccw(c,a,b) != ccw(d,a,b));
  87. 	}
  88.  
  89. 	void solve(void)
  90. 	{
  91. 		vi perm;
  92. 		FOR(i,1,n) perm.pb(i);
  93. 		do {
  94. 			int i = 1;
  95. 			for (int j : perm)
  96. 				Line[i++] = {black[i],white[j]};
  97. 			FOR(i,1,n)
  98. 				FOR(j,i+1,n)
  99. 					if (calc(Line[i].fi,Line[i].se,Line[j].fi,Line[j].se))
  100. 						goto li;
  101. 			for (int j : perm) cout << j << endl;
  102. 			return;
  103. 			li:;
  104. 		} while (next_permutation(all(perm)));
  105. 		cout << -1;
  106. 	}
  107.  
  108. }
  109.  
  110. namespace sub2 {
  111.  
  112. 	int source,sink,match[N],val;
  113. 	lb ans;
  114.  
  115. 	struct MaxFlowMinCost {
  116. 		int flow[N][N],cap[N][N],trace[N];
  117. 		lb cost[N][N],dist[N];
  118. 		vi g[N];
  119. 		bool visited[N];
  120.  
  121. 		void addEdge(int u, int v, int x, lb y)
  122. 		{
  123. 			cap[u][v] = x;
  124. 			cost[u][v] = cost[v][u] = y;
  125. 			g[u].pb(v); g[v].pb(u);
  126. 		}
  127.  
  128. 		bool FordBellman()
  129. 		{
  130. 			FOR(i,source,sink) 
  131. 			{
  132. 				dist[i] = oo;
  133. 				trace[i] = -1;
  134. 			}
  135. 			queue<int> q;
  136. 			q.push(source);
  137. 			dist[source] = 0;
  138. 			while (!q.empty())
  139. 			{
  140. 				int u = q.front();
  141. 				q.pop();
  142. 				visited[u] = false;
  143. 				for (int v : g[u])
  144. 					if (flow[u][v] < cap[u][v])
  145. 					{
  146. 						int newCost = cost[u][v]*(flow[u][v] >= 0 ? 1 : -1);
  147. 						if (minimize(dist[v],dist[u]+newCost))
  148. 						{
  149. 							trace[v] = u;
  150. 							if (!visited[v])
  151. 							{
  152. 								visited[v] = true;
  153. 								q.push(v);
  154. 							}
  155. 						}
  156. 					}
  157. 			}
  158. 			return dist[sink] < oo;
  159. 		}
  160.  
  161. 		void inc()
  162. 		{	
  163. 			int i = sink, del = oo;
  164. 			while (i != source)
  165. 			{
  166. 				minimize(del,(flow[trace[i]][i] >= 0 ? cap[trace[i]][i]-flow[trace[i]][i] : -flow[trace[i]][i]));
  167. 				i = trace[i];
  168. 			}
  169. 			minimize(del,val);
  170. 			i = sink;
  171. 			while (i != source)
  172. 			{
  173. 				flow[trace[i]][i] += del;
  174. 				flow[i][trace[i]] -= del;
  175. 				i = trace[i];
  176. 			}
  177. 			val -= del;
  178. 			ans += del*dist[sink];
  179. 			if (!val)
  180. 			{
  181. 				FOR(i,1,n)
  182. 					FOR(j,1,n)
  183. 						if (flow[i][j+n] > 0)
  184. 							match[i] = j;
  185. 				FOR(i,1,n) cout << match[i] << endl;
  186. 				exit(0);
  187. 			}
  188. 		}
  189.  
  190. 		void calc()
  191. 		{
  192. 			ans = 0;
  193. 			while (FordBellman()) inc();
  194. 			cout << -1;
  195. 		}
  196. 	} dinic;
  197.  
  198. 	lb getDist(ii a, ii b) {
  199. 		return sqrt(sqr(a.fi-b.fi)+sqr(a.se-b.se));
  200. 	}
  201.  
  202. 	void solve(void)
  203. 	{	
  204. 		val = n;
  205. 		source = 0, sink = 2*n+1;
  206. 		FOR(i,1,n) dinic.addEdge(source,i,1,0);
  207. 		FOR(i,1,n)
  208. 			FOR(j,1,n)
  209. 				dinic.addEdge(i,j+n,1,getDist(black[i],white[j]));
  210. 		FOR(i,1,n) dinic.addEdge(i+n,sink,1,0);
  211. 		dinic.calc();
  212. 	}
  213.  
  214. }
  215.  
  216. bool M2;
  217. signed main()
  218. {
  219.     fast;
  220.     if (fopen(name".inp","r"))
  221.     {
  222.     	freopen(name".inp","r",stdin);
  223.     	freopen(name".out","w",stdout);
  224.     }
  225.     cin >> n;
  226.     FOR(i,1,n) cin >> black[i];
  227.     FOR(i,1,n) cin >> white[i];
  228.     // if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  229.     sub2::solve();
  230.     time();
  231.     memory();
  232.     return 0;
  233. }
  234. // ██░ ██  █    ██  ███▄    █   ▄████
  235. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  236. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  237. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  238. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  239. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  240. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  241. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  242. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5884KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
stderr
copy 
-------------Time:6.262ms.
5.17741 MB
https://ideone.com/F1TZxc
language:
C++14 (gcc 8.3)
created:
4 days 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!