AtCoder Grand Contest 012

Submission #1359104

Source codeソースコード

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef pair<int,int> pi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
#define Rep(i,a,b) for (int i=(a);i<(b);i++)
#define Per(i,a,b) for (int i=(a);i>(b);i--)
//debug
#define deb printf("begin\n");
#define dee printf("end\n");
#define def printf("find\n");
#define dey printf("Yes\n");
#define den printf("No\n");
#define dew printf("wrong\n");
void read(int&x){
	x=0;int f=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if (ch=='-')f=-1,ch=getchar();
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=f;
}
//--------------------------head--------------------------//

#define logn 19
#define maxn 200005
int n,v,a[maxn];
int bit[logn],cntbit;

int lowbit(int x){return x&(-x);}


int toL[maxn][logn],fL[1<<logn];
void workL(){
	Rep(j,0,cntbit){toL[1][j]=1;rep(i,1+1,n)
		if (a[i]-a[i-1]<=bit[j])toL[i][j]=toL[i-1][j];
		else toL[i][j]=i;
	}
	/*
	Rep(j,0,cntbit){
		rep(i,1,n)printf("%d ",toL[i][j]);printf("\n");
	}*/
	Rep(i,0,1<<cntbit)fL[i]=n+1;
	Rep(i,0,1<<cntbit){
		for (int j=i;j;j-=lowbit(j))
			fL[i]=min(fL[i],toL[fL[i-lowbit(j)]-1][(int)log2(lowbit(j))]);
	}
	// Rep(i,0,1<<cntbit)printf("%d ",fL[i]);printf("\n");
}

int toR[maxn][logn],fR[1<<logn];
void workR(){
	Rep(j,0,cntbit){toR[n][j]=n;per(i,n-1,1)
		if (a[i+1]-a[i]<=bit[j])toR[i][j]=toR[i+1][j];
		else toR[i][j]=i;
	}
	/*
	Rep(j,0,cntbit){
		rep(i,1,n)printf("%d ",toR[i][j]);printf("\n");
	}*/
	Rep(i,0,1<<cntbit)fR[i]=1-1;
	Rep(i,0,1<<cntbit){
		for (int j=i;j;j-=lowbit(j)){
			// printf("%d %d %d\n",i,lowbit(j),(int)log2(lowbit(j)));
			fR[i]=max(fR[i],toR[fR[i-lowbit(j)]+1][(int)log2(lowbit(j))]);
		}
	}
	// Rep(i,0,1<<cntbit)printf("%d ",fR[i]);printf("\n");
}

int f[maxn][logn];
void work(){
	Rep(i,1,n)f[i][0]=a[i+1]-a[i];
	Rep(j,1,logn)Rep(i,1,n-(1<<j)+1)
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	/*
	Rep(j,0,logn){
		Rep(i,1,n-(1<<j)+1)
			printf("%d ",f[i][j]);
		printf("\n");
	}*/
}
int getmax(int L,int R){
	int j=(int)log2(R-L+1);
	return max(f[L][j],f[R-(1<<j)+1][j]);
}

int num_possible[maxn];
int main(){
	//freopen("Camel and Oases.in","r",stdin);
	//freopen("Camel and Oases.out","w",stdout);
	read(n);read(v);rep(i,1,n)read(a[i]);
	for (int i=v;i;i>>=1)bit[cntbit++]=i>>1;
	//rep(i,1,n)printf("%d ",a[i]);printf("\n");
	//Rep(i,0,cntbit)printf("%d ",bit[i]);printf("\n");
	workL();workR();work();
	Rep(i,0,1<<cntbit){
		int R=fL[i]-1,L=fR[((1<<cntbit)-1)^i]+1;
		//printf("%d %d %d %d %d\n",i,((1<<cntbit)-1)^i,L,R,getmax(L,R-1));
		if (L>R){rep(i,1,n)printf("Possible\n");return 0;}
		if (L==R||getmax(L,R-1)<=v)num_possible[L]++,num_possible[R+1]--;
	}
	//rep(i,1,n)printf("%d ",num_possible[i]);printf("\n");
	rep(i,1,n)num_possible[i]+=num_possible[i-1];
	rep(i,1,n)if (num_possible[i])printf("Possible\n");else printf("Impossible\n");
	return 0;
}

Submission

Task問題 E - Camel and Oases
User nameユーザ名 Dream_Reality
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000
Source lengthソースコード長 3252 Byte
File nameファイル名
Exec time実行時間 117 ms
Memory usageメモリ使用量 52480 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 1000 / 1000 00_example_01.txt,00_example_02.txt,00_example_03.txt,01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,33.txt,34.txt,35.txt,36.txt,37.txt,38.txt,39.txt,40.txt,41.txt,42.txt,43.txt,44.txt,45.txt,46.txt,47.txt,48.txt,49.txt,50.txt,51.txt,52.txt,53.txt,54.txt,55.txt,56.txt,57.txt,58.txt,59.txt,60.txt,61.txt,62.txt,63.txt,64.txt,65.txt,66.txt,67.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 2 ms 8320 KB
00_example_02.txt AC 2 ms 8320 KB
00_example_03.txt AC 2 ms 8320 KB
01.txt AC 48 ms 8448 KB
02.txt AC 13 ms 8448 KB
03.txt AC 48 ms 8448 KB
04.txt AC 13 ms 8448 KB
05.txt AC 48 ms 8320 KB
06.txt AC 58 ms 16256 KB
07.txt AC 19 ms 16128 KB
08.txt AC 55 ms 16128 KB
09.txt AC 20 ms 16128 KB
10.txt AC 52 ms 11264 KB
11.txt AC 32 ms 16256 KB
12.txt AC 52 ms 13568 KB
13.txt AC 115 ms 52480 KB
14.txt AC 48 ms 8320 KB
15.txt AC 13 ms 8320 KB
16.txt AC 47 ms 8320 KB
17.txt AC 11 ms 8320 KB
18.txt AC 41 ms 8320 KB
19.txt AC 24 ms 8320 KB
20.txt AC 57 ms 16256 KB
21.txt AC 19 ms 16128 KB
22.txt AC 56 ms 16256 KB
23.txt AC 21 ms 16256 KB
24.txt AC 45 ms 13568 KB
25.txt AC 31 ms 16128 KB
26.txt AC 56 ms 16128 KB
27.txt AC 115 ms 52480 KB
28.txt AC 57 ms 16256 KB
29.txt AC 19 ms 16128 KB
30.txt AC 56 ms 16256 KB
31.txt AC 30 ms 13952 KB
32.txt AC 52 ms 13568 KB
33.txt AC 31 ms 16128 KB
34.txt AC 55 ms 16128 KB
35.txt AC 117 ms 52480 KB
36.txt AC 48 ms 8320 KB
37.txt AC 12 ms 8320 KB
38.txt AC 48 ms 8320 KB
39.txt AC 13 ms 8320 KB
40.txt AC 41 ms 8320 KB
41.txt AC 24 ms 8320 KB
42.txt AC 41 ms 8320 KB
43.txt AC 24 ms 8320 KB
44.txt AC 48 ms 8320 KB
45.txt AC 24 ms 8320 KB
46.txt AC 18 ms 13952 KB
47.txt AC 54 ms 16128 KB
48.txt AC 29 ms 13952 KB
49.txt AC 54 ms 16000 KB
50.txt AC 29 ms 13824 KB
51.txt AC 53 ms 13824 KB
52.txt AC 29 ms 13824 KB
53.txt AC 53 ms 13952 KB
54.txt AC 29 ms 13824 KB
55.txt AC 56 ms 16128 KB
56.txt AC 17 ms 13568 KB
57.txt AC 47 ms 16000 KB
58.txt AC 30 ms 14080 KB
59.txt AC 52 ms 13568 KB
60.txt AC 30 ms 16128 KB
61.txt AC 54 ms 14080 KB
62.txt AC 30 ms 13952 KB
63.txt AC 54 ms 14080 KB
64.txt AC 30 ms 16128 KB
65.txt AC 54 ms 16128 KB
66.txt AC 2 ms 8320 KB
67.txt AC 2 ms 8320 KB