Submission #1118984

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( auto itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

pair<pair<int,pii>,pair<int,pii> > ak[N];  
int n;
set<pair<int,pii> > mkd,umkd;
int d,fl;
pair<int,pii> opp(pair<int,pii> a){
  int id = a.Y.X;
  if(ak[id].X==a) return ak[id].Y;
  else return ak[id].X;
}
int check(pair<int,pii> a){
  set<pair<int,pii> > :: iterator it=mkd.lower_bound(a),it1;
  it1=it;
  it++;
  if(it!=mkd.end()){
    if((*it).X-a.X<d) return 0;
  }
  if(it1!=mkd.begin()){
    it1--;
    if(a.X-(*it1).X<d) return 0;
  }
  return 1;
}
void mark(pair<int,pii> a){
  //printf("%d %d %d\n",a.X,a.Y.X,a.Y.Y);
  umkd.erase(a); umkd.erase(opp(a));
  mkd.insert(a);
  if(!check(a)) {
    fl=0; return;
  }

  while(1){
    set<pair<int,pii> > :: iterator it=umkd.lower_bound(a);
    if(it!=umkd.end()){
      
      if((*it).X-a.X<d){
        mark(opp(*it));
      }else break;
    }else break;
    if(fl==0||!check(a)) return ;
  }
  while(1){
    set<pair<int,pii> > :: iterator it=umkd.lower_bound(a);
    if(it!=umkd.begin()){
      it--;
      if(a.X-(*it).X<d){
        mark(opp(*it));
      }else break;
    }else break;
    if(fl==0||!check(a)) return ;
  }
}
void restore(){
  foreach(mkd,it){
    umkd.insert(*it);
    umkd.insert(opp(*it));
  }
  mkd.clear();
}
int calc(int _d){
  d=_d;
  umkd.clear(); mkd.clear();
  REP(i,n) umkd.insert(ak[i].X),umkd.insert(ak[i].Y);
  while(umkd.size()){
    fl=1;
   // printf("%d\n",d);
    mkd.clear();
    int id = (*umkd.begin()).Y.X;
    mark(ak[id].X);
    if(fl==0) restore();
    else continue;
    fl=1;
    mark(ak[id].Y);
    if(fl==0)  return 0;
  }
  return 1;
}
int main(){
  srand(time(NULL));  
  scanf("%d",&n);
  REP(i,n){
    int x,y;scanf("%d%d",&x,&y);
    if(x>y) swap(x,y);
    ak[i].X=mp(x,mp(i,0));
    ak[i].Y=mp(y,mp(i,1));
  }
  int l=0,r=mod;
  while(l<r){
    int m=((l+r)>>1)+1;
   // m=4;
    if(calc(m)) l = m ; else r=m-1;
  //  break;
  }
  printf("%d\n",l); 
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:115:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:117:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int x,y;scanf("%d%d",&x,&y);
                                ^

Judge Result