Submission #1727399


Source Code Expand

//Camel and Oases
#include <cstdio>
#include <algorithm>
using namespace std;
int const N=1e5+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;
        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

Submission Time
Task E - Camel and Oases
User vjudge3
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2069 Byte
Status RE
Exec Time 582 ms
Memory 139648 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41: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:45: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

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 22
WA × 32
RE × 1
OLE × 15
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 1 ms 2176 KB
00_example_02.txt AC 1 ms 2176 KB
00_example_03.txt AC 1 ms 2176 KB
01.txt WA 62 ms 8320 KB
02.txt AC 20 ms 7296 KB
03.txt WA 58 ms 8320 KB
04.txt AC 19 ms 7296 KB
05.txt WA 59 ms 8320 KB
06.txt WA 97 ms 8832 KB
07.txt AC 31 ms 7680 KB
08.txt WA 92 ms 8704 KB
09.txt AC 29 ms 7680 KB
10.txt WA 94 ms 8576 KB
11.txt OLE 537 ms 139008 KB
12.txt WA 92 ms 8576 KB
13.txt WA 43 ms 8704 KB
14.txt WA 53 ms 8320 KB
15.txt AC 17 ms 7296 KB
16.txt WA 49 ms 8320 KB
17.txt AC 16 ms 7296 KB
18.txt AC 49 ms 8320 KB
19.txt WA 27 ms 7936 KB
20.txt WA 100 ms 8832 KB
21.txt AC 33 ms 7552 KB
22.txt OLE 574 ms 139648 KB
23.txt AC 32 ms 7680 KB
24.txt AC 97 ms 8576 KB
25.txt OLE 522 ms 139008 KB
26.txt WA 100 ms 8704 KB
27.txt WA 43 ms 8704 KB
28.txt OLE 576 ms 139648 KB
29.txt AC 33 ms 7552 KB
30.txt OLE 582 ms 139648 KB
31.txt OLE 530 ms 139008 KB
32.txt WA 97 ms 8704 KB
33.txt OLE 530 ms 139008 KB
34.txt WA 99 ms 8704 KB
35.txt RE 110 ms 512 KB
36.txt WA 54 ms 8320 KB
37.txt AC 20 ms 7296 KB
38.txt WA 56 ms 8320 KB
39.txt WA 20 ms 7296 KB
40.txt AC 52 ms 8320 KB
41.txt WA 29 ms 7808 KB
42.txt AC 54 ms 8320 KB
43.txt WA 29 ms 7808 KB
44.txt WA 54 ms 8320 KB
45.txt WA 28 ms 7808 KB
46.txt AC 30 ms 7552 KB
47.txt WA 92 ms 8704 KB
48.txt OLE 524 ms 139008 KB
49.txt WA 95 ms 8576 KB
50.txt OLE 524 ms 139008 KB
51.txt WA 318 ms 84992 KB
52.txt OLE 522 ms 139008 KB
53.txt WA 91 ms 8704 KB
54.txt OLE 519 ms 139008 KB
55.txt WA 92 ms 8704 KB
56.txt AC 22 ms 7552 KB
57.txt AC 85 ms 8704 KB
58.txt OLE 516 ms 139008 KB
59.txt WA 82 ms 8576 KB
60.txt OLE 516 ms 139008 KB
61.txt WA 299 ms 80256 KB
62.txt OLE 532 ms 139008 KB
63.txt WA 84 ms 8576 KB
64.txt OLE 520 ms 139008 KB
65.txt WA 85 ms 8704 KB
66.txt AC 1 ms 2176 KB
67.txt AC 1 ms 2176 KB