oj.uz

Submission #331788

# Submission time Handle Problem Language Result Execution time Memory
331788 2020-11-30T06:44:48 Z daniel920712 Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 1179 ms 65540 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <map>
#include <utility>
#include <algorithm>
#include <stack>
using namespace std;
char all[1148576];
char tt[25];
int con[25][1100005];
int ans=0;
int N;
void F(int x,int y,int z)
{
    if(x==N)
    {
        if(z%2==0) ans+=con[N][y];
        else ans-=con[N][y];
        return;
    }
    if(tt[x]=='1')
    {
        F(x+1,y+(1<<(N-x-1)),z);
        F(x+1,y,z+1);
    }
    else if(tt[x]=='0') F(x+1,y,z);
    else F(x+1,y+(1<<(N-x-1)),z);

}
void F2(int x,int y)
{
    if(x==N)
    {
        ans+=(all[y]-'0');
        return;
    }
    if(tt[x]=='?')
    {
        F2(x+1,y);
        F2(x+1,y+(1<<(N-x-1)));
    }
    else F2(x+1,y+(1<<(N-x-1))*(tt[x]-'0'));
}
int main()
{
    int M,i,j,ok,a,b;
    scanf("%d %d",&N,&M);
    scanf("%s",all);
    for(i=0;i<(1<<N);i++) con[0][i]=all[i]-'0';
    for(i=0;i<N;i++)
    {
        for(j=0;j<(1<<N);j++)
        {
            con[i+1][j]=con[i][j];
            if(j&(1<<i)) con[i+1][j]+=con[i][j-(1<<i)];
        }
    }
    while(M--)
    {
        scanf("%s",tt);
        ans=0;
        a=0;
        b=0;
        for(i=0;i<N;i++)
        {
            if(tt[i]=='?') a++;
            else b++;
        }
        if(a>b) F(0,0,0);
        else F2(0,0);
        printf("%d\n",ans);

    }

	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:49:15: warning: unused variable 'ok' [-Wunused-variable]
   49 |     int M,i,j,ok,a,b;
      |               ^~
snake_escaping.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%s",all);
      |     ~~~~~^~~~~~~~~~
snake_escaping.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 631 ms 14700 KB Output is correct
12 Correct 514 ms 14920 KB Output is correct
13 Correct 391 ms 14312 KB Output is correct
14 Correct 378 ms 14192 KB Output is correct
15 Correct 466 ms 15212 KB Output is correct
16 Correct 508 ms 14512 KB Output is correct
17 Correct 450 ms 14700 KB Output is correct
18 Correct 295 ms 16236 KB Output is correct
19 Correct 257 ms 13292 KB Output is correct
20 Correct 553 ms 14976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 631 ms 14700 KB Output is correct
12 Correct 514 ms 14920 KB Output is correct
13 Correct 391 ms 14312 KB Output is correct
14 Correct 378 ms 14192 KB Output is correct
15 Correct 466 ms 15212 KB Output is correct
16 Correct 508 ms 14512 KB Output is correct
17 Correct 450 ms 14700 KB Output is correct
18 Correct 295 ms 16236 KB Output is correct
19 Correct 257 ms 13292 KB Output is correct
20 Correct 553 ms 14976 KB Output is correct
21 Correct 1179 ms 18836 KB Output is correct
22 Correct 740 ms 18924 KB Output is correct
23 Correct 634 ms 17936 KB Output is correct
24 Correct 609 ms 17688 KB Output is correct
25 Correct 563 ms 19764 KB Output is correct
26 Correct 753 ms 18476 KB Output is correct
27 Correct 700 ms 18284 KB Output is correct
28 Correct 297 ms 20588 KB Output is correct
29 Correct 280 ms 16876 KB Output is correct
30 Correct 974 ms 18836 KB Output is correct
31 Correct 1158 ms 18660 KB Output is correct
32 Correct 792 ms 18780 KB Output is correct
33 Correct 435 ms 17748 KB Output is correct
34 Correct 578 ms 17772 KB Output is correct
35 Correct 710 ms 18160 KB Output is correct
36 Correct 280 ms 17004 KB Output is correct
37 Correct 1076 ms 18592 KB Output is correct
38 Correct 306 ms 16652 KB Output is correct
39 Correct 586 ms 18032 KB Output is correct
40 Correct 574 ms 17772 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 631 ms 14700 KB Output is correct
12 Correct 514 ms 14920 KB Output is correct
13 Correct 391 ms 14312 KB Output is correct
14 Correct 378 ms 14192 KB Output is correct
15 Correct 466 ms 15212 KB Output is correct
16 Correct 508 ms 14512 KB Output is correct
17 Correct 450 ms 14700 KB Output is correct
18 Correct 295 ms 16236 KB Output is correct
19 Correct 257 ms 13292 KB Output is correct
20 Correct 553 ms 14976 KB Output is correct
21 Correct 1179 ms 18836 KB Output is correct
22 Correct 740 ms 18924 KB Output is correct
23 Correct 634 ms 17936 KB Output is correct
24 Correct 609 ms 17688 KB Output is correct
25 Correct 563 ms 19764 KB Output is correct
26 Correct 753 ms 18476 KB Output is correct
27 Correct 700 ms 18284 KB Output is correct
28 Correct 297 ms 20588 KB Output is correct
29 Correct 280 ms 16876 KB Output is correct
30 Correct 974 ms 18836 KB Output is correct
31 Correct 1158 ms 18660 KB Output is correct
32 Correct 792 ms 18780 KB Output is correct
33 Correct 435 ms 17748 KB Output is correct
34 Correct 578 ms 17772 KB Output is correct
35 Correct 710 ms 18160 KB Output is correct
36 Correct 280 ms 17004 KB Output is correct
37 Correct 1076 ms 18592 KB Output is correct
38 Correct 306 ms 16652 KB Output is correct
39 Correct 586 ms 18032 KB Output is correct
40 Correct 574 ms 17772 KB Output is correct
41 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -