Submission #1118807


Source Code Expand

#include <bits/stdc++.h>

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, sel[10005];
PII s[10005], pp[10005];

struct info{
	int id, fb, pos;
	bool operator<(const info &k) const{
		return pos < k.pos;
	}
};

info u[20005];

int q[20005], ql, qr, ok;

void dfs(int id, int cho, int d){
	ql = qr = 0;
	q[++qr] = id;
	sel[id] = cho;
	while(ql < qr){
		int cur = q[++ql], cp;
		if(sel[cur] == 0) cp = pp[cur].fi;
		else cp = pp[cur].se;
		
		FD(i, cp - 1, 1){
			if(u[i].pos + d <= u[cp].pos) break;
			if(sel[u[i].id] == -1){
				sel[u[i].id] = 1 - u[i].fb;
				q[++qr] = u[i].id;
			}
			else if(sel[u[i].id] == u[i].fb){
				ok = false;
				return;
			}
		}
		FI(i, cp + 1, n + n){
			if(u[i].pos - d >= u[cp].pos) break;
			if(sel[u[i].id] == -1){
				sel[u[i].id] = 1 - u[i].fb;
				q[++qr] = u[i].id;
			}
			else if(sel[u[i].id] == u[i].fb){
				ok = false;
				return;
			}
		}
	}
	return;
}

bool good(int d){
	//preliminary test
	int cnt = 0, pd = -d;
	FI(i, 1, n + n){
		if(u[i].pos >= pd + d){
			pd = u[i].pos;
			cnt++;
		}
	}
	if(cnt < n) return false;
	
	FI(i, 1, n) sel[i] = -1;
	FI(i, 1, n) if(sel[i] == -1){
		ok = true;
		dfs(i, 0, d);
		if(!ok){
			FI(i, 1, qr) sel[q[i]] = -1;
			ok = true;
			dfs(i, 1, d);
			if(!ok) return false;
		}
	}
	return true;
}

int main(){
	scanf("%d", &n);
	FI(i, 1, n){
		scanf("%d %d", &s[i].fi, &s[i].se);
		if(s[i].fi > s[i].se) swap(s[i].fi, s[i].se);
		u[i + i - 1] = (info){i, 0, s[i].fi};
		u[i + i] = (info){i, 1, s[i].se};
	}
	
	sort(s + 1, s + n + 1);
	sort(u + 1, u + n + n + 1);
	
	FI(i, 1, n + n){
		if(u[i].fb == 0) pp[u[i].id].fi = i;
		else pp[u[i].id].se = i;
	}
	
	int l = 0, r = 1000000001;
	while(r - l > 1){
		int m = (l + r) >> 1;
		if(good(m)) l = m;
		else r = m;
	}
	printf("%d\n", l);
	return 0;
}

Submission Info

Submission Time
Task F - Flags
User alex20030190
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2155 Byte
Status AC
Exec Time 1155 ms
Memory 768 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:95:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &s[i].fi, &s[i].se);
                                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 30
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 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
01.txt AC 1 ms 256 KB
02.txt AC 1 ms 256 KB
03.txt AC 1 ms 256 KB
04.txt AC 1 ms 256 KB
05.txt AC 1 ms 256 KB
06.txt AC 8 ms 640 KB
07.txt AC 8 ms 640 KB
08.txt AC 7 ms 640 KB
09.txt AC 2 ms 256 KB
10.txt AC 1 ms 256 KB
11.txt AC 1 ms 256 KB
12.txt AC 1 ms 256 KB
13.txt AC 1 ms 256 KB
14.txt AC 9 ms 640 KB
15.txt AC 10 ms 640 KB
16.txt AC 9 ms 640 KB
17.txt AC 2 ms 256 KB
18.txt AC 1 ms 256 KB
19.txt AC 523 ms 768 KB
20.txt AC 146 ms 768 KB
21.txt AC 5 ms 640 KB
22.txt AC 5 ms 640 KB
23.txt AC 5 ms 640 KB
24.txt AC 5 ms 640 KB
25.txt AC 4 ms 640 KB
26.txt AC 1155 ms 768 KB
27.txt AC 1 ms 256 KB