Submission #21269316

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

int main()
{
  int n, d;
  cin >> n >> d;

  vector<ll> x(n);
  vector<ll> y(n);
  for (int i = 0; i < n; i++){
    cin >> x[i] >> y[i];
  }

  two_sat ts(n);

  for (int i = 0; i < n; i++){
    for (int j = i + 1; j < n; j++){
      if (abs(x[i] - x[j]) < d){
	ts.add_clause(i, false, j, false);
      }
      if (abs(y[i] - x[j]) < d){
	ts.add_clause(i, true, j, false);
      }
      if (abs(x[i] - y[j]) < d){
	ts.add_clause(i, false, j, true);
      }
      if (abs(y[i] - y[j]) < d){
	ts.add_clause(i, true, j, true);
      }
    }
  }

  if (!ts.satisfiable()){
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  auto answer = ts.answer();
  for (int i = 0; i < n; i++){
    if (answer[i])
      cout << x[i] << endl;
    else
      cout << y[i] << endl;
  }
  
  return 0;
}

Submission Info

Judge Result