Submission #1162489


Source Code Expand

	#include<cstdio>
	#include<algorithm>
	#include<cstring>
	#include<iostream>
	#include<vector>
	#include<set>
	#include<map>
	#include<bitset>
	#include<cmath>
	#include<string>
	
	#define ls (t<<1)
	#define rs ((t<<1)+1)
	#define mid ((l+r)>>1)
	#define fi first
	#define se second
	#define mk make_pair
	#define pb push_back
	
	#define N 100005
	#define M 200005
	#define seed 23333
	
	using namespace std;
	const int inf=(int)1e9;
	int i,j,m,n,p,k,A[N],B[N],l;
	map<pair<int,int>,int>mp;
	vector<int>v[M];
	int f[2][N],ans,sum[N],size[2],now,last;
	int RE()
	{
			puts("-1");
			exit(0);
	}
	int main()
	{
			scanf("%d",&n); ans=2*n-2;
			for (i=1;i<=n;++i) 
			{
					scanf("%d%d",&A[i],&B[i]);
					mp[mk(A[i],B[i])]=1;
					if (i!=1&&!A[i]) RE();
					if (i!=2&&!B[i]) RE();
			}
			for (i=1;i<=n;++i)
			{
					if (i!=1&&mp.find(mk(A[i]-1,B[i]))==mp.end()&&
							mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
							mp.find(mk(A[i]-1,B[i]+1))==mp.end()) RE();
					if (i!=2&&mp.find(mk(A[i],B[i]-1))==mp.end()&&
							mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
							mp.find(mk(A[i]+1,B[i]-1))==mp.end()) RE();
					v[A[i]+B[i]].pb(A[i]);
			}
			for (i=1;i<=2*n;++i)
					if (v[i].size())
					{
							A[0]=B[0]=0;
							for (j=0;j<(int)v[i].size();++j) A[++A[0]]=v[i][j],B[++B[0]]=v[i][j]; 
							sort(B+1,B+B[0]+1); B[0]=unique(B+1,B+B[0]+1)-(B+1);
							for (j=1;j<=B[0];++j) sum[j]=0;
							for (j=1;j<=A[0];++j) sum[lower_bound(B+1,B+B[0]+1,A[j])-B]++;
							size[0]=size[1]=now=last=0; now=1;
							size[1]=sum[1];
							if (mp.find(mk(B[1]-1,i-B[1]-1))!=mp.end())
							for (j=0;j<=size[now];++j) f[now][j]=size[now]-j;
							else for (j=0;j<=size[now];++j) f[now][j]=0;
							for (j=2;j<=B[0];++j)
							{
									now^=1; last=now^1;
									for (l=0;l<=size[now];++l) f[now][l]=0;
									if (mp.find(mk(B[j]-1,i-B[j]-1))==mp.end())
									{
										  for (l=0;l<=size[last];++l)
										  	 f[now][sum[j]]=max(f[now][sum[j]],f[last][l]+(B[j]-B[j-1]==1)*min(sum[j],l));
									}
									else 
									{
										 int Max=-inf;
										 for (l=0;l<=size[now];++l)
										{
												if (l<=size[last]) Max=max(Max,f[last][l]+(B[j]-B[j-1]==1)*l);
												f[now][l]=Max;
										}
										 Max=-inf;
										 for (l=max(size[last],size[now]);l>=0;--l)
										 {
										 		if (l<=size[last]) Max=max(Max,f[last][l]);
										 		if (l<=size[now])
										 		f[now][l]=max(f[now][l],Max+(B[j]-B[j-1]==1)*l);
										 }
										 for (l=0;l<=size[now];++l)
										 	f[now][l]+=(size[now]-l);
									}
									size[now]=sum[j];
							}
							int Max=0;
							for (j=0;j<=size[now];++j) Max=max(Max,f[now][j]);
							ans-=Max;
					}
			printf("%d\n",ans);
	}

Submission Info

Submission Time
Task A - Distance Pairs
User qiaoranliqu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2830 Byte
Status WA
Exec Time 152 ms
Memory 15104 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&n); ans=2*n-2;
                  ^
./Main.cpp:40:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&A[i],&B[i]);
                               ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 22
WA × 13
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 56 ms 12032 KB
01-02.txt AC 19 ms 5760 KB
01-03.txt AC 3 ms 5248 KB
01-04.txt AC 3 ms 5248 KB
01-05.txt WA 3 ms 5248 KB
01-06.txt WA 16 ms 5888 KB
01-07.txt WA 66 ms 6656 KB
01-08.txt WA 58 ms 6656 KB
01-09.txt WA 37 ms 6400 KB
01-10.txt WA 27 ms 6528 KB
01-11.txt WA 58 ms 6528 KB
01-12.txt WA 53 ms 6400 KB
01-13.txt WA 141 ms 13568 KB
01-14.txt AC 152 ms 12924 KB
01-15.txt AC 128 ms 15104 KB
01-16.txt AC 23 ms 6648 KB
01-17.txt AC 23 ms 6396 KB
01-18.txt AC 20 ms 6648 KB
01-19.txt WA 148 ms 13056 KB
01-20.txt WA 130 ms 11520 KB
01-21.txt WA 132 ms 11520 KB
01-22.txt WA 104 ms 9212 KB
01-23.txt AC 38 ms 6272 KB
01-24.txt AC 49 ms 6528 KB
01-25.txt AC 16 ms 5632 KB
01-26.txt AC 5 ms 5376 KB
01-27.txt AC 16 ms 5760 KB
01-28.txt AC 14 ms 5632 KB
01-29.txt AC 3 ms 5248 KB
01-30.txt AC 3 ms 5248 KB
01-31.txt AC 3 ms 5248 KB
sample-01.txt AC 3 ms 5248 KB
sample-02.txt AC 3 ms 5248 KB