Submission #1847609


Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define x first
#define y second

template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}
template<typename T>inline void check_max(T a,T &b){if(a>b)b=a;}

namespace yy
{
	const int N=201000,M=N*20;

	struct bit
	{
		bool s[N];
		inline int lowbit(int x){return x&(-x);}
		void init(){memset(s,0,sizeof(s));}
		void inc(int p){p++;for(;p<N;p+=lowbit(p))s[p]=1;}
		bool query(int p){p++;bool ret=0;for(;p;p-=lowbit(p))ret|=s[p];return ret;}
	}T;

	struct node
	{
		int L,R,ty;
		node(int a=0,int b=0,int c=0):L(a),R(b),ty(c){}
		bool operator < (const node &h) const {return L==h.L?R==h.R?ty<h.ty:R<h.R:L>h.L;}
	};

	node s[M];

	int begin[N],next[M*2],to[M*2],w[M*2];
	int pos[N];
	int n,m,e,tot,cnt,S;

	void add(int x,int y,int z,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		w[e]=z;
		if(k)add(y,x,z,0);
	}

	void work(int dis,int dep)
	{
		for(int L=1,R;L<=n;L=R+1)
		{
			for(R=L;R<n && pos[R+1]-pos[R]<=dis;R++);
			if(dep>1)add(L,R,dep-1);
			else s[++tot]=node(L,R,1);
		}
	}
	void initialize()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",pos+i);
		tot=0,cnt=1;
		for(int tmp=m;;tmp/=2,cnt++)
		{
			work(tmp,cnt);
			if(!tmp)break;
		}
		S=1<<(cnt-1);
	}

	inline int ins(int k,int i){return k|(1<<(i-1));}
	int f[N*4],g[N*4];

	void dp()
	{
		for(int i=0;i<S;i++)
			f[i]=0,g[i]=n+1;
		for(int k=0;k<S;k++)
		{
			int p=f[k]+1;
			for(int i=begin[p];i;i=next[i])
				if(!(k&(1<<(w[i]-1))))
					check_max(to[i],f[ins(k,w[i])]);
			p=g[k]-1;
			for(int i=begin[p];i;i=next[i])
				if(!(k&(1<<(w[i]-1))))
					check_min(to[i],g[ins(k,w[i])]);
		}
	}

	bool ans[N];

	void solve()
	{
		initialize();
		dp();
		
		for(int k=0;k<S;k++)
			s[++tot]=node(f[k]+1,g[S-k-1]-1,0);
		std::sort(s+1,s+tot+1);
		T.init();

		for(int i=1;i<=tot;i++)
		{
			if(!s[i].ty)T.inc(s[i].R);
			else if(T.query(s[i].R))
			{
				for(int j=s[i].L;j<=s[i].R;j++)
					ans[j]=1;
			}
		}
		for(int i=1;i<=n;i++)
			printf("%s\n",ans[i]?"Possible":"Impossible");
	}
}

int main()
{
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	yy::solve();
	return 0;
}

Submission Info

Submission Time
Task A - AtCoder Group Contest
User Demerzel_IV
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2309 Byte
Status RE
Exec Time 185 ms
Memory 149632 KB

Compile Error

./Main.cpp: In function ‘void yy::initialize()’:
./Main.cpp:58:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^
./Main.cpp:60:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",pos+i);
                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 300
Status
WA × 1
RE × 1
WA × 7
RE × 5
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt
Case Name Status Exec Time Memory
00_example_01.txt WA 17 ms 57728 KB
00_example_02.txt RE 170 ms 149632 KB
01.txt RE 170 ms 149632 KB
02.txt RE 113 ms 61440 KB
03.txt WA 17 ms 57728 KB
04.txt WA 48 ms 58240 KB
05.txt RE 171 ms 149632 KB
06.txt RE 185 ms 149632 KB
07.txt WA 27 ms 58624 KB
08.txt WA 41 ms 66944 KB
09.txt WA 37 ms 60800 KB
10.txt WA 39 ms 62848 KB