CODE FESTIVAL 2016 Exhibition(Parallel)

Submission #1162485

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[1]-1,i-B[1]-1))==mp.end())
								{
									  for (l=0;l<=size[last];++l)
									  	 f[now][sum[j]]=max(f[now][sum[j]],f[last][l]+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]+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+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ソースコード長 2677 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

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

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

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 55 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 150 ms 12924 KB
01-15.txt AC 128 ms 15104 KB
01-16.txt AC 22 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 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 13 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