fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 2000 + 10;
  6.  
  7. int a[N];
  8. vector<int> G[N];
  9. int dfn[N], low[N], stk[N], be[N];
  10. bool instk[N];
  11. int n, scn, t, top, d, s;
  12.  
  13. int neg(int x) {
  14. 	if (x > n) return x - n;
  15. 	else return x + n;
  16. }
  17.  
  18. bool ok(int x, int y) {
  19. 	return abs(a[x] - a[y]) >= d;
  20. }
  21.  
  22. void check(int i, int j) {
  23. 	if (!ok(i, j)) {
  24. 		G[i].push_back(neg(j));
  25. 		G[j].push_back(neg(i));
  26. 	}
  27. 	if (!ok(i, neg(j))) {
  28. 		G[i].push_back(j);
  29. 		G[neg(j)].push_back(neg(i));
  30. 	}
  31. 	if (!ok(neg(i), j)) {
  32. 		G[neg(i)].push_back(neg(j));
  33. 		G[j].push_back(i);
  34. 	}
  35. 	if (!ok(neg(i), neg(j))) {
  36. 		G[neg(i)].push_back(j);
  37. 		G[neg(j)].push_back(i);
  38. 	}
  39. }
  40.  
  41. void dfs(int u) {
  42. 	dfn[u] = low[u] = ++ t;
  43. 	stk[top++] = u;
  44. 	instk[u] = true;
  45. 	for (int v: G[u]) {
  46. 		if (dfn[v]) {
  47. 			if (instk[v]) low[u] = min(low[u], dfn[v]);
  48. 			continue;
  49. 		}
  50. 		dfs(v);
  51. 		low[u] = min(low[u], low[v]);
  52. 	}
  53. 	if (low[u] == dfn[u]) {
  54. 		scn ++;
  55. 		while (true) {
  56. 			int v = stk[--top];
  57. 			instk[v] = false;
  58. 			be[v] = scn;
  59. 			if (v == u) break;
  60. 		}
  61. 	}
  62. }
  63.  
  64. int main() {
  65. 	cin >> n >> d;
  66. 	for (int i=1; i<=n; i++) cin >> a[i] >> a[i+n];
  67. 	for (int i=1; i<n; i++) {
  68. 		for (int j=i+1; j<=n; j++) check(i, j);
  69. 	}
  70. 	for (int i=1; i<=2*n; i++) if (!dfn[i]) dfs(i);
  71. 	bool ok = true;
  72. 	for (int i=1; i<=n; i++) {
  73. 		if (be[i] == be[i+n]) {
  74. 			ok = false;
  75. 			break;
  76. 		}
  77. 	}
  78. 	if (ok) {
  79. 		printf("Yes\n");
  80. 		for (int i=1; i<=n; i++) if (be[i] < be[i+n]) printf("%d\n", a[i]); else printf("%d\n", a[i+n]); 
  81. 	}
  82. 	else printf("No\n"); 
  83. 	return 0;
  84. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/LYgCNw
language:
C++ (gcc 8.3)
created:
6 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!