#include<stdio.h>
#include<stdlib.h>
int hi(int a,int b){return a>b?a:b;}
unsigned X=12345;int rand_(){return(X*=3)>>1;}
#define N 1<<20
int alc,A[N],B[N],L[N],R[N],S[N];
int tt(int x)
{
int p=++alc;
A[p]=x;
B[p]=rand_();
L[p]=R[p]=0;
S[p]=1;
return p;
}
void ts(int v,int*l,int*r,int k)
{
if(!v){*l=*r=0;return;}
if(S[L[v]]+1<=k)
{
ts(R[v],R+v,r,k-S[L[v]]-1);
*l=v;
}
else
{
ts(L[v],l,L+v,k);
*r=v;
}
S[v]=S[L[v]]+S[R[v]]+1;
}
void tm(int*v,int l,int r)
{
if(!l||!r){*v=l^r;return;}
if(B[l]>B[r])
{
tm(L+r,l,L[r]);
*v=r;
}
else
{
tm(R+l,R[l],r);
*v=l;
}
S[*v]=S[L[*v]]+S[R[*v]]+1;
}
int to(int v,int k)
{
if(!v)return 0;
if(A[v]<=k)return 1+S[L[v]]+to(R[v],k);
return to(L[v],k);
}
int n,m,d,a[1<<20],ao,b[1<<20],*eh[N],eo[N];
void append(int i,int j)
{
int o=eo[i]++;
if(o>=2&&(o&(o-1))==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
eh[i][o]=j;
}
void tp(int v)
{
if(!v)return;
tp(L[v]);
printf(" %d ", A[v]);
tp(R[v]);
}
int main()
{
scanf("%d%d%d",&n,&d,&m);
for (int i=1;i<N;++i)eh[i]=(int*)malloc(2*sizeof**eh);
for (int i=1;i<=m;++i)scanf("%d",b+i),append(b[i],i);
for(int i=1;i<=n-d;++i)for(int j=0;j<eo[i];++j)a[ao++]=eh[i][j];
int l=1,r=m;
while(l<=r)
{
int o=(l+r)>>1,ok=1,t=alc=0;
for (int i=1;i<=o;++i)tm(&t,t,tt(1));
for(int i=1;ok&&i<=n-d;++i)
{
//if(o==2) { printf(" Day %d (%d)\n",i,eo[i]); }
for(int j=0;ok&&j<eo[i];++j)
{
int ded=i+d;
int t1,t2,t3,t4,cc=to(t,ded);
if(cc==0){ok=0;break;}
ts(t,&t3,&t4,cc);
ts(t3,&t2,&t1,cc-1);
if(A[t1]<i)A[t1]=i;
++A[t1];
tm(&t3,t2,t4);
int dd=to(t3,A[t1]);
ts(t3,&t2,&t4,dd);
tm(&t3,t2,t1);
tm(&t,t3,t4);
//if(o==2) { tp(t); puts(""); }
}
}
if(ok) r=o-1;
else l=o+1;
}
alc=0;
int t=0;
for(int i=1;i<=r+1;++i)tm(&t,t,tt(1));
for(int i=1;i<=n-d;++i)
{
for(int j=0;j<eo[i];++j)
{
int ded=d+i,t1,t2,t3,t4,cc=to(t,ded);
ts(t,&t3,&t4,cc);
ts(t3,&t2,&t1,cc-1);
if(A[t1]<i)A[t1]=i;
//printf(" : %d AT %d\n",eh[i][j],A[t1]);
append(100001+(A[t1]++),eh[i][j]);
tm(&t3,t2,t4);
int dd=to(t3,A[t1]);
ts(t3,&t2,&t4,dd);
tm(&t3,t2,t1);
tm(&t,t3,t4);
}
}
printf("%d\n",r+1);
for(int i=1;i<=n;++i)
{
//printf("%d",eo[i+100001]);
for (int j = 0; j < eo[i+100001];++j)printf("%d ",eh[i+100001][j]);
puts("0");
}
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
Compilation message
jobs.cpp: In function 'int main()':
jobs.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d%d%d",&n,&d,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | for (int i=1;i<=m;++i)scanf("%d",b+i),append(b[i],i);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1102 ms |
54696 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1062 ms |
54704 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1063 ms |
54920 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1055 ms |
54876 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1053 ms |
54868 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1004 ms |
54864 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1053 ms |
54856 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1054 ms |
54872 KB |
Time limit exceeded |
| 9 |
Runtime error |
748 ms |
56108 KB |
Memory limit exceeded |
| 10 |
Runtime error |
798 ms |
56316 KB |
Memory limit exceeded |
| 11 |
Runtime error |
612 ms |
56132 KB |
Memory limit exceeded |
| 12 |
Execution timed out |
1068 ms |
56156 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1076 ms |
61784 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1068 ms |
62032 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1072 ms |
62548 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1069 ms |
65368 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1049 ms |
65448 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1038 ms |
65536 KB |
Time limit exceeded |
| 19 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Execution timed out |
1067 ms |
65464 KB |
Time limit exceeded |
