CODE FESTIVAL 2016 Exhibition(Parallel)

Submission #1162489

Source codeソースコード

	#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

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

Compiler messageコンパイルメッセージ

./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]);
^

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 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
01-06.txt WA
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
01-11.txt WA
01-12.txt WA
01-13.txt WA
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
01-20.txt WA
01-21.txt WA
01-22.txt WA
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