Submission #1727471


Source Code Expand

//Camel and Oases
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long lint;
int const N=2e5+10;
int const S=1<<18;
int n,V;
lint 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("%lld",&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]=0,f2[s]=n+1;
    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;
        if(f) for(int j=fr;j<=to;j++)
            if(j==1) printf("Possible");
            else printf("\nPossible");
        else for(int j=fr;j<=to;j++)
            if(j==1) printf("Impossible");
            else printf("\nImpossible");
    }
    return 0;
}

Submission Info

Submission Time
Task E - Camel and Oases
User vjudge5
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2243 Byte
Status WA
Exec Time 793 ms
Memory 150528 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43: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:47:65: 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("%lld",&d[i]),d[i-1]=d[i]-d[i-1];
                                                                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 34
WA × 11
OLE × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 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
Case Name Status Exec Time Memory
00_example_01.txt AC 2 ms 6272 KB
00_example_02.txt AC 2 ms 6272 KB
00_example_03.txt AC 3 ms 8320 KB
01.txt WA 71 ms 19712 KB
02.txt AC 24 ms 17536 KB
03.txt WA 67 ms 19072 KB
04.txt AC 23 ms 17536 KB
05.txt WA 68 ms 18688 KB
06.txt OLE 735 ms 149632 KB
07.txt AC 35 ms 17792 KB
08.txt OLE 727 ms 149632 KB
09.txt AC 33 ms 17792 KB
10.txt OLE 736 ms 149632 KB
11.txt AC 58 ms 18816 KB
12.txt OLE 738 ms 149632 KB
13.txt OLE 753 ms 150528 KB
14.txt WA 61 ms 18560 KB
15.txt AC 21 ms 17536 KB
16.txt WA 58 ms 18560 KB
17.txt AC 20 ms 17536 KB
18.txt WA 59 ms 18560 KB
19.txt AC 36 ms 18560 KB
20.txt OLE 733 ms 149632 KB
21.txt AC 37 ms 17792 KB
22.txt OLE 731 ms 149632 KB
23.txt AC 35 ms 17792 KB
24.txt OLE 733 ms 149632 KB
25.txt AC 63 ms 18816 KB
26.txt OLE 738 ms 149632 KB
27.txt OLE 758 ms 150528 KB
28.txt OLE 738 ms 149632 KB
29.txt AC 37 ms 17792 KB
30.txt OLE 746 ms 149632 KB
31.txt AC 78 ms 18688 KB
32.txt OLE 758 ms 149632 KB
33.txt AC 72 ms 18816 KB
34.txt OLE 738 ms 149632 KB
35.txt OLE 793 ms 150528 KB
36.txt WA 65 ms 18560 KB
37.txt AC 23 ms 17536 KB
38.txt WA 68 ms 18688 KB
39.txt AC 24 ms 17536 KB
40.txt WA 66 ms 18560 KB
41.txt AC 42 ms 18560 KB
42.txt WA 64 ms 18560 KB
43.txt AC 43 ms 18560 KB
44.txt WA 66 ms 18560 KB
45.txt AC 41 ms 18560 KB
46.txt AC 33 ms 17792 KB
47.txt OLE 724 ms 149632 KB
48.txt AC 61 ms 18816 KB
49.txt OLE 747 ms 149632 KB
50.txt AC 64 ms 18688 KB
51.txt OLE 722 ms 149632 KB
52.txt AC 66 ms 18688 KB
53.txt OLE 728 ms 149632 KB
54.txt AC 60 ms 18688 KB
55.txt OLE 724 ms 149632 KB
56.txt AC 26 ms 17664 KB
57.txt OLE 742 ms 149632 KB
58.txt AC 50 ms 18816 KB
59.txt OLE 711 ms 149632 KB
60.txt AC 53 ms 18816 KB
61.txt OLE 718 ms 149632 KB
62.txt AC 56 ms 18816 KB
63.txt OLE 718 ms 149632 KB
64.txt AC 51 ms 18816 KB
65.txt OLE 732 ms 149632 KB
66.txt AC 2 ms 6272 KB
67.txt AC 2 ms 6272 KB