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
2017-12-10 12:02:49+0900
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
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