| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 58947 | 2018-07-19T21:25:32 Z | TadijaSebez | Snake Escaping (JOI18_snake_escaping) | C++11 | 487 ms | 66560 KB |
#include <stdio.h>
const int N=1<<20;
int dp0[N],dp1[N],pc[N];
char s[N],t[20];
int min(int a, int b){ return a>b?b:a;}
int abs(int x){ return x>0?x:-x;}
int main()
{
int n,q,i,mask;
for(i=1;i<N;i++) pc[i]=pc[i-(i&-i)]+1;
scanf("%i %i",&n,&q);
scanf("%s",s);
for(i=0;i<(1<<n);i++)
{
dp1[i]=dp0[i]=s[i]-'0';
}
for(i=0;i<n;i++)
{
for(mask=0;mask<(1<<n);mask++)
{
if((mask>>i)&1) dp0[mask^(1<<i)]+=dp0[mask];
else dp1[mask^(1<<i)]+=dp1[mask];
}
}
while(q--)
{
scanf("%s",t);
int a=0,b=0,c=0;
for(i=0;i<n;i++)
{
if(t[n-i-1]=='0') a+=1<<i;
else if(t[n-i-1]=='1') b+=1<<i;
else c+=1<<i;
}
int ans=0;
if(pc[a]<=min(pc[b],pc[c]))
{
for(mask=a;;mask=(mask-1)&a)
{
//printf("a:%i %i\n",a,mask);
int go=((1<<n)-1)^mask^c;
if((pc[mask]&1)==(pc[a]&1)) ans+=dp0[go];
else ans-=dp0[go];
if(!mask) break;
}
}
else if(pc[b]<=min(pc[a],pc[c]))
{
for(mask=b;;mask=(mask-1)&b)
{
//printf("b:%i %i\n",b,mask);
if((pc[mask]&1)==(pc[b]&1)) ans+=dp1[mask|c];
else ans-=dp1[mask|c];
if(!mask) break;
}
}
else
{
for(mask=c;;mask=(mask-1)&c)
{
//printf("c:%i %i\n",c,mask);
ans+=s[mask|b]-'0';
if(!mask) break;
}
}
printf("%i\n",abs(ans));
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 4472 KB | Output is correct |
| 2 | Correct | 6 ms | 4584 KB | Output is correct |
| 3 | Correct | 6 ms | 4584 KB | Output is correct |
| 4 | Correct | 6 ms | 4584 KB | Output is correct |
| 5 | Correct | 6 ms | 4584 KB | Output is correct |
| 6 | Correct | 6 ms | 4768 KB | Output is correct |
| 7 | Correct | 7 ms | 4768 KB | Output is correct |
| 8 | Correct | 6 ms | 4768 KB | Output is correct |
| 9 | Correct | 6 ms | 4768 KB | Output is correct |
| 10 | Correct | 6 ms | 4768 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 4472 KB | Output is correct |
| 2 | Correct | 6 ms | 4584 KB | Output is correct |
| 3 | Correct | 6 ms | 4584 KB | Output is correct |
| 4 | Correct | 6 ms | 4584 KB | Output is correct |
| 5 | Correct | 6 ms | 4584 KB | Output is correct |
| 6 | Correct | 6 ms | 4768 KB | Output is correct |
| 7 | Correct | 7 ms | 4768 KB | Output is correct |
| 8 | Correct | 6 ms | 4768 KB | Output is correct |
| 9 | Correct | 6 ms | 4768 KB | Output is correct |
| 10 | Correct | 6 ms | 4768 KB | Output is correct |
| 11 | Correct | 361 ms | 13904 KB | Output is correct |
| 12 | Correct | 316 ms | 13904 KB | Output is correct |
| 13 | Correct | 356 ms | 13904 KB | Output is correct |
| 14 | Correct | 333 ms | 13904 KB | Output is correct |
| 15 | Correct | 359 ms | 13904 KB | Output is correct |
| 16 | Correct | 357 ms | 13904 KB | Output is correct |
| 17 | Correct | 340 ms | 13904 KB | Output is correct |
| 18 | Correct | 226 ms | 14844 KB | Output is correct |
| 19 | Correct | 259 ms | 14844 KB | Output is correct |
| 20 | Correct | 284 ms | 14844 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 4472 KB | Output is correct |
| 2 | Correct | 6 ms | 4584 KB | Output is correct |
| 3 | Correct | 6 ms | 4584 KB | Output is correct |
| 4 | Correct | 6 ms | 4584 KB | Output is correct |
| 5 | Correct | 6 ms | 4584 KB | Output is correct |
| 6 | Correct | 6 ms | 4768 KB | Output is correct |
| 7 | Correct | 7 ms | 4768 KB | Output is correct |
| 8 | Correct | 6 ms | 4768 KB | Output is correct |
| 9 | Correct | 6 ms | 4768 KB | Output is correct |
| 10 | Correct | 6 ms | 4768 KB | Output is correct |
| 11 | Correct | 361 ms | 13904 KB | Output is correct |
| 12 | Correct | 316 ms | 13904 KB | Output is correct |
| 13 | Correct | 356 ms | 13904 KB | Output is correct |
| 14 | Correct | 333 ms | 13904 KB | Output is correct |
| 15 | Correct | 359 ms | 13904 KB | Output is correct |
| 16 | Correct | 357 ms | 13904 KB | Output is correct |
| 17 | Correct | 340 ms | 13904 KB | Output is correct |
| 18 | Correct | 226 ms | 14844 KB | Output is correct |
| 19 | Correct | 259 ms | 14844 KB | Output is correct |
| 20 | Correct | 284 ms | 14844 KB | Output is correct |
| 21 | Correct | 334 ms | 16500 KB | Output is correct |
| 22 | Correct | 368 ms | 16544 KB | Output is correct |
| 23 | Correct | 420 ms | 16544 KB | Output is correct |
| 24 | Correct | 487 ms | 16544 KB | Output is correct |
| 25 | Correct | 421 ms | 31360 KB | Output is correct |
| 26 | Correct | 433 ms | 43424 KB | Output is correct |
| 27 | Correct | 461 ms | 57204 KB | Output is correct |
| 28 | Runtime error | 464 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 29 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 4472 KB | Output is correct |
| 2 | Correct | 6 ms | 4584 KB | Output is correct |
| 3 | Correct | 6 ms | 4584 KB | Output is correct |
| 4 | Correct | 6 ms | 4584 KB | Output is correct |
| 5 | Correct | 6 ms | 4584 KB | Output is correct |
| 6 | Correct | 6 ms | 4768 KB | Output is correct |
| 7 | Correct | 7 ms | 4768 KB | Output is correct |
| 8 | Correct | 6 ms | 4768 KB | Output is correct |
| 9 | Correct | 6 ms | 4768 KB | Output is correct |
| 10 | Correct | 6 ms | 4768 KB | Output is correct |
| 11 | Runtime error | 79 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 4472 KB | Output is correct |
| 2 | Correct | 6 ms | 4584 KB | Output is correct |
| 3 | Correct | 6 ms | 4584 KB | Output is correct |
| 4 | Correct | 6 ms | 4584 KB | Output is correct |
| 5 | Correct | 6 ms | 4584 KB | Output is correct |
| 6 | Correct | 6 ms | 4768 KB | Output is correct |
| 7 | Correct | 7 ms | 4768 KB | Output is correct |
| 8 | Correct | 6 ms | 4768 KB | Output is correct |
| 9 | Correct | 6 ms | 4768 KB | Output is correct |
| 10 | Correct | 6 ms | 4768 KB | Output is correct |
| 11 | Correct | 361 ms | 13904 KB | Output is correct |
| 12 | Correct | 316 ms | 13904 KB | Output is correct |
| 13 | Correct | 356 ms | 13904 KB | Output is correct |
| 14 | Correct | 333 ms | 13904 KB | Output is correct |
| 15 | Correct | 359 ms | 13904 KB | Output is correct |
| 16 | Correct | 357 ms | 13904 KB | Output is correct |
| 17 | Correct | 340 ms | 13904 KB | Output is correct |
| 18 | Correct | 226 ms | 14844 KB | Output is correct |
| 19 | Correct | 259 ms | 14844 KB | Output is correct |
| 20 | Correct | 284 ms | 14844 KB | Output is correct |
| 21 | Correct | 334 ms | 16500 KB | Output is correct |
| 22 | Correct | 368 ms | 16544 KB | Output is correct |
| 23 | Correct | 420 ms | 16544 KB | Output is correct |
| 24 | Correct | 487 ms | 16544 KB | Output is correct |
| 25 | Correct | 421 ms | 31360 KB | Output is correct |
| 26 | Correct | 433 ms | 43424 KB | Output is correct |
| 27 | Correct | 461 ms | 57204 KB | Output is correct |
| 28 | Runtime error | 464 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 29 | Halted | 0 ms | 0 KB | - |