CODE FESTIVAL 2016 Exhibition

Submission #1306055

Source codeソースコード

#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[ i ].yy == last + 1 ) del = min( now, left ), ret -= del;
			if( cnt.find( mp( c[ i ].xx - c[ i ].yy - 1, c[ i ].yy - 1 ) ) != cnt.end() ) ret -= now - del, now = del;
			last = c[ i ].yy; left = now;
		}
	}
	return printf( "%d\n", ret ), 0;
}

Submission

Task問題 A - Distance Pairs
User nameユーザ名 wxh010910
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1966 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
All 0 / 1500 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 54 ms 8064 KB
01-02.txt AC 15 ms 1792 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 12 ms 1152 KB
01-07.txt AC 39 ms 2048 KB
01-08.txt AC 40 ms 2176 KB
01-09.txt AC 30 ms 1920 KB
01-10.txt AC 21 ms 1792 KB
01-11.txt AC 34 ms 1920 KB
01-12.txt AC 32 ms 1920 KB
01-13.txt AC 103 ms 8064 KB
01-14.txt AC 96 ms 8064 KB
01-15.txt AC 97 ms 8064 KB
01-16.txt AC 13 ms 1792 KB
01-17.txt AC 12 ms 1792 KB
01-18.txt AC 12 ms 1792 KB
01-19.txt AC 106 ms 8064 KB
01-20.txt AC 100 ms 6912 KB
01-21.txt AC 101 ms 6912 KB
01-22.txt AC 76 ms 4480 KB
01-23.txt WA
01-24.txt AC 40 ms 2176 KB
01-25.txt AC 9 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