Submission #1306049


Source Code Expand

#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define fill( x, y ) memset( x, y, sizeof x )
#define copy( x, y ) memcpy( x, y, sizeof x )
using namespace std;

typedef long long LL;
typedef pair < int, int > pa;

inline int read()
{
	int sc = 0, f = 1; char ch = getchar();
	while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }
	while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();
	return sc * f;
}

const int MAXN = 100005;

int n, a[MAXN], b[MAXN];
map < pa, bool > cnt;
pa c[MAXN];

inline void GG() { puts( "-1" ); exit( 0 ); }

int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#endif
	n = read();
	for( int i = 1 ; i <= n ; i++ )
	{
		a[ i ] = read(), b[ i ] = read(), c[ i ] = mp( a[ i ] + b[ i ], b[ i ] );
		if( !a[ i ] && i != 1 ) GG();
		if( !b[ i ] && i != 2 ) GG();
		cnt[ mp( a[ i ], b[ i ] ) ] = 1;
	}
	if( a[ 1 ] || b[ 2 ] ) GG();
	sort( c + 1, c + n + 1 );
	int ret = n - 1 << 1;
	for( int l = 1, r = 1 ; l <= n ; l = r )
	{
		while( r <= n && c[ r ].xx == c[ l ].xx )
		{
			int x = c[ r ].xx - c[ r ].yy, y = c[ r ].yy;
			if( x )
			{
				bool flag = false;
				for( int d = -1 ; d <= 1 ; d++ ) if( cnt.find( mp( x - 1, y + d ) ) != cnt.end() ) flag = true;
				if( !flag ) GG();
			}
			if( y )
			{
				bool flag = true;
				for( int d = -1 ; d <= 1 ; d++ ) if( cnt.find( mp( x + d, y - 1 ) ) != cnt.end() ) flag = true;
				if( !flag ) GG();
			}
			r++;
		}
		for( int i = l, j = l, last = 0, left = 0 ; i <= r ; i = j )
		{
			while( j <= r && c[ j ].yy == c[ i ].yy ) j++;
			int now = j - i, del = 0;
			if( c[ j ].yy == last + 1 ) del = min( now, left ), ret -= del;
			if( cnt.find( mp( c[ j ].xx - c[ j ].yy - 1, c[ j ].yy - 1 ) ) != cnt.end() ) ret -= now - del, now = del;
			last = c[ j ].yy; last = now;
		}
	}
	return printf( "%d\n", ret ), 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User wxh010910
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1968 Byte
Status WA
Exec Time 104 ms
Memory 8064 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 14
WA × 21
Set Name Test Cases
sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 54 ms 8064 KB
01-02.txt AC 15 ms 1792 KB
01-03.txt WA 1 ms 256 KB
01-04.txt WA 1 ms 256 KB
01-05.txt WA 2 ms 256 KB
01-06.txt WA 11 ms 1152 KB
01-07.txt WA 38 ms 2048 KB
01-08.txt WA 40 ms 2176 KB
01-09.txt WA 29 ms 1920 KB
01-10.txt WA 21 ms 1792 KB
01-11.txt WA 32 ms 1920 KB
01-12.txt WA 30 ms 1920 KB
01-13.txt WA 104 ms 8064 KB
01-14.txt WA 93 ms 8064 KB
01-15.txt WA 98 ms 8064 KB
01-16.txt WA 12 ms 1792 KB
01-17.txt WA 12 ms 1792 KB
01-18.txt WA 12 ms 1792 KB
01-19.txt WA 103 ms 8064 KB
01-20.txt WA 99 ms 6912 KB
01-21.txt WA 101 ms 6912 KB
01-22.txt WA 75 ms 4480 KB
01-23.txt WA 40 ms 2176 KB
01-24.txt AC 39 ms 2176 KB
01-25.txt AC 10 ms 1408 KB
01-26.txt AC 3 ms 512 KB
01-27.txt AC 10 ms 1408 KB
01-28.txt AC 9 ms 1280 KB
01-29.txt AC 1 ms 256 KB
01-30.txt AC 1 ms 256 KB
01-31.txt AC 1 ms 256 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB