Submission #1845274
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
T i=0;char c;
while(!isdigit(c=getchar())&&c!='-');
bool flag=c=='-';
flag?c=getchar():0;
while(i=i*10-'0'+c,isdigit(c=getchar()));
return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=20010;
int n,cup;
int x[N],lst[N];
namespace G{
const int N=20010*4,E=(N<<3)+N*40;//todo
int to[E],bro[E],head[N],e,n;
int dfn[N],low[N],bln[N],tim;
inline int nn(){
return ++n;
}
inline void init(){
memset(head+1,-1,n<<2);
memset(dfn+1,0,n<<2);
e=tim=0;
}
inline void ae(int u,int v){
to[e]=v,bro[e]=head[u],head[u]=e++;
}
int stk[N],ss=0;
bool instk[N];
void tarjan(int x){
dfn[x]=low[x]=++tim;
stk[ss++]=x,instk[x]=true;
for(int i=head[x],v;~i;i=bro[i]){
if(dfn[v=to[i]]){
if(instk[v]){
apmin(low[x],dfn[v]);
}
}else{
tarjan(v);
apmin(low[x],low[v]);
}
}
if(dfn[x]==low[x]){
int v;
do{
v=stk[--ss];
instk[v]=false;
bln[v]=x;
}while(v!=x);
}
}
}
namespace seg{
struct Node;
typedef Node* node;
struct Node{
int l,m,r;
node lson,rson;
int p[2];
}*rt;
node build(int l,int r){
static node n=new Node[N<<1];
node x=n++;
x->l=l,x->m=(l+r)>>1,x->r=r;
if(l==r){
x->p[0]=lst[l],x->p[1]=cup-lst[l];
}else{
x->p[0]=G::nn(),x->p[1]=G::nn();
x->lson=build(l,x->m);
x->rson=build(x->m+1,r);
}
return x;
}
void putedge(node x){
if(x->l!=x->r){
G::ae(x->p[1],x->lson->p[1]);
G::ae(x->lson->p[0],x->p[0]);
G::ae(x->p[1],x->rson->p[1]);
G::ae(x->rson->p[0],x->p[0]);
putedge(x->lson);
putedge(x->rson);
}
}
void ae(node x,int p,int l,int r){
if(x->l==l&&x->r==r){
G::ae(p,x->p[1]);
G::ae(x->p[0],cup-p);
}else if(r<=x->m){
ae(x->lson,p,l,r);
}else if(x->m<l){
ae(x->rson,p,l,r);
}else{
ae(x->lson,p,l,x->m);
ae(x->rson,p,x->m+1,r);
}
}
}
inline bool judge(int d){
G::init();
seg::putedge(seg::rt);
for(int i=1,j=i;i<cup;i++){
for(;x[lst[i]]-x[lst[j]]>=d;j++);
if(j<i){
seg::ae(seg::rt,lst[i],j,i-1);
}
}
for(int i=1;i<=G::n;i++){
if(G::dfn[i]==0){
G::tarjan(i);
}
}
for(int i=1;i<cup;i++){
if(G::bln[i]==G::bln[cup-i])return false;
}
for(int i=cup;i<=G::n;i+=2){
if(G::bln[i]==G::bln[i+1])return false;
}
return true;
}
inline bool lcmp(int a,int b){
return x[a]<x[b];
}
inline int Main(){
n=ni,cup=(n<<1)+1;
for(int i=1;i<=n;i++){
x[i]=ni,x[cup-i]=ni;
}
for(int i=1;i<cup;i++){
lst[i]=i;
}
sort(lst+1,lst+cup,lcmp);
G::n=n<<1;
seg::rt=seg::build(1,n<<1);
int l=0,r=x[lst[cup-1]]-x[lst[1]];
while(l<r){
int m=((l+r)>>1)+1;
if(judge(m)){
l=m;
}else{
r=m-1;
}
}
return l;
}
int main(){
printf("%d\n",Main());
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
sshockwave |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
3173 Byte |
Status |
AC |
Exec Time |
299 ms |
Memory |
13568 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
2304 KB |
00_example_02.txt |
AC |
1 ms |
256 KB |
00_example_03.txt |
AC |
2 ms |
2304 KB |
01.txt |
AC |
5 ms |
2560 KB |
02.txt |
AC |
3 ms |
2432 KB |
03.txt |
AC |
2 ms |
2304 KB |
04.txt |
AC |
2 ms |
2304 KB |
05.txt |
AC |
2 ms |
2432 KB |
06.txt |
AC |
162 ms |
9472 KB |
07.txt |
AC |
161 ms |
9344 KB |
08.txt |
AC |
162 ms |
9344 KB |
09.txt |
AC |
5 ms |
2560 KB |
10.txt |
AC |
3 ms |
2432 KB |
11.txt |
AC |
2 ms |
2304 KB |
12.txt |
AC |
2 ms |
2304 KB |
13.txt |
AC |
2 ms |
2432 KB |
14.txt |
AC |
161 ms |
11392 KB |
15.txt |
AC |
160 ms |
11392 KB |
16.txt |
AC |
160 ms |
11392 KB |
17.txt |
AC |
6 ms |
2560 KB |
18.txt |
AC |
3 ms |
2432 KB |
19.txt |
AC |
177 ms |
9344 KB |
20.txt |
AC |
177 ms |
9344 KB |
21.txt |
AC |
222 ms |
11392 KB |
22.txt |
AC |
223 ms |
11392 KB |
23.txt |
AC |
299 ms |
13440 KB |
24.txt |
AC |
200 ms |
13440 KB |
25.txt |
AC |
251 ms |
13568 KB |
26.txt |
AC |
201 ms |
11392 KB |
27.txt |
AC |
2 ms |
2304 KB |