fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. #define SZ(x) ((int)x.size())
  8. #define ALL(V) V.begin(), V.end()
  9. #define L_B lower_bound
  10. #define U_B upper_bound
  11. #define pb push_back
  12.  
  13. #define FOR(i, a, b) for (int i=a; i<(b); i++)
  14. #define F0R(i, a) for (int i=0; i<(a); i++)
  15. #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
  16. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  17.  
  18. using namespace std;
  19. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  20. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  21. const int MAXN = (int)1e5 + 42;
  22.  
  23. /// Benq 2-Sat and scc
  24. template<int SZ> struct scc {
  25. 	vector<int> adj[SZ], radj[SZ], todo, allComp;
  26. 	int N, comp[SZ];
  27. 	bitset<SZ> visit;
  28.  
  29. 	void clear(int n)
  30. 	{
  31. 		for(int i = 0; i < n; i++)
  32. 			adj[i].clear(), radj[i].clear();
  33. 		allComp.clear();
  34. 		todo.clear();
  35. 	}
  36.  
  37. 	void clear_2()
  38. 	{
  39. 		allComp.clear();
  40. 		todo.clear();
  41. 	}
  42.  
  43. 	void dfs(int v) {
  44. 		visit[v] = 1; 
  45. 		for (int w: adj[v]) if (!visit[w]) dfs(w);
  46. 		todo.pb(v);
  47. 	}
  48.  
  49. 	void dfs2(int v, int val) {
  50. 		comp[v] = val;
  51. 		for (int w: radj[v]) if (comp[w] == -1) dfs2(w,val);
  52. 	}
  53.  
  54. 	void addEdge(int a, int b) { adj[a].pb(b), radj[b].pb(a); }
  55.  
  56. 	void genSCC() {
  57. 		F0R(i,N) comp[i] = -1, visit[i] = 0;
  58. 		F0R(i,N) if (!visit[i]) dfs(i);
  59. 		reverse(ALL(todo)); // toposort 
  60. 		for (int i: todo) if (comp[i] == -1) dfs2(i,i), allComp.pb(i);
  61. 	}
  62. };
  63.  
  64. template<int SZ> struct twosat {
  65. 	scc<2*SZ> S;
  66. 	int N;
  67.  
  68. 	void SetTrue(int x) { S.addEdge(x^1,x); }
  69.  
  70. 	void NotBoth1(int x, int y)
  71. 	{
  72. 		S.addEdge(x, y^1);
  73. 		S.addEdge(y, x^1);
  74. 	}
  75.  
  76. 	void SetBothSame(int x, int y)
  77. 	{
  78. 		//cout << "SAME" << x / 2 << " " << y / 2 << endl;
  79.  
  80. 		S.addEdge(x, y);
  81. 		S.addEdge(y, x);
  82.  
  83. 		S.addEdge(x ^ 1, y ^ 1);
  84. 		S.addEdge(y ^ 1, x ^ 1);
  85. 	}
  86.  
  87. 	int tmp[2*SZ];
  88. 	bitset<SZ> ans;
  89.  
  90. 	void init(int n)
  91. 	{
  92. 		S.clear(2 * n);
  93. 		N = n;
  94. 		for(int i = 0; i < SZ; i++)
  95. 			tmp[2 * i] = tmp[2 * i + 1] = 0, ans[i] = 0;
  96. 	}
  97.  
  98. 	void clear_sat()
  99. 	{
  100. 		S.clear_2();
  101. 		for(int i = 0; i < SZ; i++)
  102. 			tmp[2 * i] = tmp[2 * i + 1] = 0, ans[i] = 0;
  103. 	}
  104.  
  105. 	bool solve() {
  106. 		S.N = 2*N; S.genSCC();
  107. 		for (int i = 0; i < 2*N; i += 2) if (S.comp[i] == S.comp[i^1]) return 0;
  108. 		reverse(ALL(S.allComp));
  109. 		for (int i: S.allComp) if (tmp[i] == 0) 
  110. 			tmp[i] = 1, tmp[S.comp[i^1]] = -1;
  111. 		F0R(i,N) if (tmp[S.comp[2*i]] == 1) ans[i] = 1;
  112. 		return 1;
  113. 	}
  114. };
  115.  
  116. int n, X[MAXN], Y[MAXN];
  117. map<int, vector<pair<int, int> > > on_x;
  118. map<int, vector<pair<int, int> > > on_y;
  119. vector<pair<pair<int, int>, int> > Vec; 
  120.  
  121. int read_int();
  122.  
  123. void read()
  124. {
  125. 	n = read_int();
  126. 	for(int i = 0; i < n; i++)
  127. 	{
  128. 		int x, y;
  129. 		x = read_int();
  130. 		y = read_int();
  131.  
  132. 		X[i] = x;
  133. 		Y[i] = y;
  134.  
  135. 		on_x[x].push_back({y, i});
  136. 		on_y[y].push_back({x, i});
  137. 		Vec.push_back({{x, y}, i});
  138. 	}
  139. }
  140.  
  141. twosat<MAXN> sat2;
  142. set<pair<int, int> > st;
  143.  
  144. bool simple_check(int64_t d)
  145. {
  146. 	sat2.init(n);
  147.  
  148. 	for(auto X: on_x)
  149. 	{
  150. 		// currently looking at |
  151.  
  152. 		int last = -2 * d - 42, il = -1;
  153. 		for(auto it: X.second)
  154. 		{
  155. 			if((int64_t)it.first - last <= d) 
  156. 			{
  157. 				sat2.SetTrue(it.second * 2);
  158. 				sat2.SetTrue(il * 2);
  159. 			}
  160. 			else if((int64_t)it.first - last <= 2 * d)
  161. 				sat2.NotBoth1(it.second * 2 + 1, il * 2 + 1);
  162.  
  163. 			last = it.first;
  164. 			il = it.second;
  165. 		}
  166. 	}
  167.  
  168. 	for(auto X: on_y)
  169. 	{
  170. 		// currently looking at -
  171.  
  172. 		int last = -2 * d - 42, il = -1;
  173. 		for(auto it: X.second)
  174. 		{
  175. 			if((int64_t)it.first - last <= d) 
  176. 			{
  177. 				sat2.SetTrue(it.second * 2 + 1);
  178. 				sat2.SetTrue(il * 2 + 1);
  179. 			}
  180. 			else if((int64_t)it.first - last <= 2 * d)
  181. 				sat2.NotBoth1(it.second * 2, il * 2);
  182.  
  183. 			last = it.first;
  184. 			il = it.second;
  185. 		}
  186. 	}
  187.  
  188. 	return sat2.solve();
  189. }
  190.  
  191. bool check(int d)
  192. {
  193. 	if(!simple_check(d)) return false;
  194.  
  195. 	sat2.clear_sat();
  196.  
  197. 	int p_l = 0;
  198. 	st.clear();
  199. 	for(int i = 0; i < n; i++)
  200. 	{
  201. 		while(Vec[i].first.first - Vec[p_l].first.first > d) st.erase({Vec[p_l].first.second, Vec[p_l].second}), p_l++;
  202.  
  203. 		int y = Vec[i].first.second, idx = Vec[i].second;
  204.  
  205. 		auto R = st.lower_bound({y, MAXN});	
  206. 		if(R != st.end() && R->first - y <= d)
  207. 			sat2.SetBothSame(R->second * 2, idx * 2);
  208.  
  209. 		if(R != st.begin())
  210. 		{
  211. 			R--;
  212. 			if(y - R->first <= d)
  213. 				sat2.SetBothSame(R->second * 2, idx * 2);
  214. 		}
  215.  
  216. 		if(i != n - 1 && Vec[i].first.first != Vec[i + 1].first.first)
  217. 		{
  218. 			if(Vec[i + 1].first.first - Vec[i].first.first > d) st.clear(), p_l = i + 1;
  219. 			else for(int j = i; j >= 0 && Vec[j].first.first == Vec[i].first.first; j--)
  220. 				st.insert({Vec[j].first.second, Vec[j].second});
  221. 		}
  222. 	}
  223.  
  224. 	return sat2.solve();
  225. }
  226.  
  227. void solve()
  228. {
  229. 	for(auto &it: on_x)
  230. 		sort(ALL(it.second));
  231. 	for(auto &it: on_y)
  232. 		sort(ALL(it.second));
  233.  
  234. 	sort(ALL(Vec));
  235.  
  236. 	if(check((int)1e9 + 42))
  237. 	{
  238. 		cout << -1 << endl;
  239. 		for(int i = 0; i < n; i++)
  240. 			cout << (sat2.ans[i] ? '-' : '|'); 
  241. 		return;
  242. 	}
  243.  
  244. 	int low = 0, high = (int)1e9, mid, ret = 0;
  245.  
  246. 	/*for(int i = 0; high - (1 << i) >= low; i++)
  247. 	  if(!check(high - (1 << i))) high -= (1 << i);
  248. 	  else 
  249. 	  { 
  250. 	  ret = high - (1 << i); 
  251. 	  low = high - (1 << i) + 1; 
  252. 	  break; 
  253. 	  }*/
  254.  
  255. 	for(int i = 0; i < n; i++)
  256. 	{
  257. 		int vert = (int)1e9, hor = (int)1e9;
  258.  
  259. 		{
  260. 			auto &V = on_x[X[i]];
  261.  
  262. 			auto L = U_B(ALL(V), make_pair(Y[i], i)) - V.begin();
  263. 			if(L != SZ(V))
  264. 				chkmin(vert, V[L].first - Y[i]);
  265.  
  266. 			L -= 2;
  267. 			if(L >= 0)
  268. 				chkmin(vert, Y[i] - V[L].first);	
  269. 		}
  270.  
  271. 		{
  272. 			auto &V = on_y[Y[i]];
  273.  
  274. 			auto L = U_B(ALL(V), make_pair(X[i], i)) - V.begin();
  275. 			if(L != SZ(V))
  276. 				chkmin(hor, V[L].first - X[i]);
  277.  
  278. 			L -= 2;
  279. 			if(L >= 0)
  280. 				chkmin(hor, X[i] - V[L].first);	
  281. 		}
  282.  
  283. 		chkmin(high, max(hor, vert));
  284. 	}
  285.  
  286. 	while(low <= high)
  287. 	{
  288. 		mid = (low + high) >> 1;
  289. 		if(check(mid))
  290. 			ret = mid, low = mid + 1;
  291. 		else
  292. 			high = mid - 1;
  293. 	}
  294.  
  295. 	check(ret);
  296. 	cout << ret << endl;
  297. 	for(int i = 0; i < n; i++)
  298. 		cout << (sat2.ans[i] ? '-' : '|'); 
  299. }
  300.  
  301. int main()
  302. {
  303. 	ios_base::sync_with_stdio(false);
  304. 	cin.tie(NULL);
  305.  
  306. 	read();
  307. 	solve();
  308. 	return 0;
  309. }
  310.  
  311. const int maxl = 100000;
  312. char buff[maxl];
  313. int ret_int, pos_buff = 0;
  314.  
  315. void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0; }
  316.  
  317. int read_int()
  318. {
  319. 	ret_int = 0;
  320. 	for(; buff[pos_buff] < '0' || buff[pos_buff] > '9'; next_char());
  321. 	for(; buff[pos_buff] >= '0' && buff[pos_buff] <= '9'; next_char())
  322. 		ret_int = ret_int * 10 + buff[pos_buff] - '0';
  323. 	return ret_int;
  324. }
Time limit exceeded #stdin #stdout 5s 27112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vbmKva
language:
C++14 (gcc 8.3)
created:
6 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!