Submission #1727407

---

Source Code Expand

//Camel and Oases
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const N=2e5+10;
int const S=1<<17;
int n,V;
int d[N];
int logV,a[20][N];
int U,f1[S],f2[S];
int upFind(int a[],int x)
{
    int L=1,R=a[0];
    while(L<R-1)
    {
        int mid=(L+R)>>1;
        if(a[mid]<=x) L=mid+1;
        if(a[mid]>x) R=mid;
    }
    if(a[L]>x) return a[L];
    else return a[R];
}
int lowFind(int a[],int x)
{
    int L=1,R=a[0];
    while(L<R-1)
    {
        int mid=(L+R)>>1;
        if(a[mid]<x) L=mid;
        if(a[mid]>=x) R=mid-1;
    }
    if(a[R]<x) return a[R]+1;
    else return a[L]+1;
}
void type(int s)
{
    for(int i=logV;i>=1;i--) printf("%d",(s>>(i-1))%2);
}
int main()
{
    scanf("%d%d",&n,&V);
    logV=0;
    while((1<<logV)<=V) logV++;
    logV++;
    for(int i=1;i<=n;i++) scanf("%d",&d[i]),d[i-1]=d[i]-d[i-1];
    d[n]=0;
    for(int i=1;i<=logV;i++)
    {
        a[i][0]=1;
        for(int j=1;j<=n;j++)
        {
            a[i][a[i][0]]=j;
            if(d[j]>(V>>(i-1))) a[i][0]++;
        }
    }
    /*for(int i=1;i<=logV;i++)
    {
    	printf("%d-%d ",1,a[i][1]);
        for(int j=2;j<=a[i][0];j++) printf("%d-%d ",a[i][j-1]+1,a[i][j]);
        printf("\n");
    }*/
    if(a[1][0]>logV)
    {
        for(int i=1;i<=n;i++) puts("Impossible");
        return 0;
    }
    U=(1<<logV)-1;
    for(int s=0;s<=U;s++) f1[s]=1,f2[s]=n;
    for(int s=0;s<=U;s+=2)
        for(int i=2;i<=logV;i++)
        {
            int s0=1<<(i-1);
            if(s&s0) continue;
            f1[s|s0]=max(f1[s|s0],upFind(a[i],f1[s]));
            f2[s|s0]=min(f2[s|s0],lowFind(a[i],f2[s]-1));
        }
    /*for(int s=0;s<=U;s+=2)
        type(s),printf("   1-%2d  %2d-%2d\n",f1[s],f2[U-s-1],n);*/
    for(int i=1;i<=a[1][0];i++)
    {
        bool f=false;
        int fr=a[1][i-1]+1,to=a[1][i];
        if(i==1) fr=1;
        for(int s=0;s<=U&&!f;s+=2)
            if(fr<=f1[s]+1 && f2[U-s-1]-1<=to) f=true;
        printf("%d-%d\n",fr,to);
        if(f) for(int j=fr;j<=to;j++) puts("Possible");
        else for(int j=fr;j<=to;j++) puts("Impossible");
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&V);
                        ^
./Main.cpp:46:63: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d",&d[i]),d[i-1]=d[i]-d[i-1];
                                                               ^

Judge Result