Submission #1162505


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;
								size[now]=sum[j];
								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);
								}
						}
						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 1500
Code Size 2728 Byte
Status AC
Exec Time 151 ms
Memory 15104 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:17: 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:30: 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 1500 / 1500
Status
AC × 2
AC × 35
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 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 AC 3 ms 5248 KB
01-06.txt AC 15 ms 5888 KB
01-07.txt AC 65 ms 6656 KB
01-08.txt AC 58 ms 6656 KB
01-09.txt AC 36 ms 6400 KB
01-10.txt AC 26 ms 6528 KB
01-11.txt AC 57 ms 6528 KB
01-12.txt AC 53 ms 6400 KB
01-13.txt AC 137 ms 13568 KB
01-14.txt AC 151 ms 12924 KB
01-15.txt AC 126 ms 15104 KB
01-16.txt AC 22 ms 6648 KB
01-17.txt AC 22 ms 6648 KB
01-18.txt AC 20 ms 6648 KB
01-19.txt AC 146 ms 13056 KB
01-20.txt AC 129 ms 11520 KB
01-21.txt AC 130 ms 11520 KB
01-22.txt AC 102 ms 9212 KB
01-23.txt AC 37 ms 6272 KB
01-24.txt AC 48 ms 6528 KB
01-25.txt AC 15 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