답안 #80254 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80254	2018-10-19T16:55:25 Z	Bodo171	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	993 ms	66560 KB

snake_escaping

#include <cstdio>


using namespace std;
const int nmax=(1<<20);
char s[20],str[nmax];
char t;
char pc[nmax];
int sub[nmax],supra[nmax];
int l,q,i,j,m0,m1,mq,ans,cnt;
char mn;
bool brk;
int main()
{
    scanf("%d%d",&l,&q);
    scanf("%s",&str);
    for(i=0;i<(1<<l);i++)
    {
        if(i!=0)
            pc[i]=pc[(i&(i-1))]+1;
        sub[i]=supra[i]=str[i]=str[i]-'0';
    }
    for(i=0;i<l;i++)
        for(j=0;j<(1<<l);j++)
           if(((1<<i)&j))
              sub[j]+=sub[(j^(1<<i))];
            else supra[j]+=supra[(j^(1<<i))];
    for(cnt=1;cnt<=q;cnt++)
    {
        scanf("%s",&s);
        m0=m1=mq=0;
        for(j=l-1;j>=0;j--)
        {
            t=s[l-1-j];
            if(t=='0') m0|=(1<<j);
            else if(t=='1') m1|=(1<<j);
             else mq|=(1<<j);
        }
        mn=pc[m0];
        if(pc[m1]<mn) mn=pc[m1];
        if(pc[mq]<mn) mn=pc[mq];
        ans=0;brk=0;
        if(mn==pc[m0])
        {
            ans=supra[m1];
            i=m0;
            while(i!=0)
            {
                if((pc[i]&1)) ans-=supra[(i|m1)];
                else ans+=supra[(i|m1)];
                i=((i-1)&m0);
            }
        }
        else
        {
            if(mn==pc[m1])
            {
                i=m1;
                while(!brk)
                {
                    if(i==0)
                        brk=1;
                    if(((pc[m1]-pc[i])&1)) ans-=sub[(i|mq)];
                    else ans+=sub[(i|mq)];
                    i=((i-1)&m1);
                }
            }
            else
            {
                    i=mq;
                    while(!brk)
                    {
                        ans+=str[(m1|i)];
                        if(i==0)
                            brk=1;
                        i=((i-1)&mq);
                    }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:16:20: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1048576]' [-Wformat=]
     scanf("%s",&str);
                ~~~~^
snake_escaping.cpp:30:22: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[20]' [-Wformat=]
         scanf("%s",&s);
                    ~~^
snake_escaping.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&l,&q);
     ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&str);
     ~~~~~^~~~~~~~~~~
snake_escaping.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&s);
         ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	576 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	576 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	266 ms	10240 KB	Output is correct
12	Correct	293 ms	11524 KB	Output is correct
13	Correct	316 ms	13068 KB	Output is correct
14	Correct	323 ms	13216 KB	Output is correct
15	Correct	311 ms	14064 KB	Output is correct
16	Correct	317 ms	14064 KB	Output is correct
17	Correct	347 ms	16892 KB	Output is correct
18	Correct	236 ms	18716 KB	Output is correct
19	Correct	265 ms	18716 KB	Output is correct
20	Correct	278 ms	18716 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	576 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	266 ms	10240 KB	Output is correct
12	Correct	293 ms	11524 KB	Output is correct
13	Correct	316 ms	13068 KB	Output is correct
14	Correct	323 ms	13216 KB	Output is correct
15	Correct	311 ms	14064 KB	Output is correct
16	Correct	317 ms	14064 KB	Output is correct
17	Correct	347 ms	16892 KB	Output is correct
18	Correct	236 ms	18716 KB	Output is correct
19	Correct	265 ms	18716 KB	Output is correct
20	Correct	278 ms	18716 KB	Output is correct
21	Correct	325 ms	18716 KB	Output is correct
22	Correct	334 ms	20196 KB	Output is correct
23	Correct	374 ms	20196 KB	Output is correct
24	Correct	405 ms	20196 KB	Output is correct
25	Correct	352 ms	22624 KB	Output is correct
26	Correct	403 ms	22624 KB	Output is correct
27	Correct	397 ms	22624 KB	Output is correct
28	Correct	302 ms	25036 KB	Output is correct
29	Correct	334 ms	25036 KB	Output is correct
30	Correct	356 ms	25176 KB	Output is correct
31	Correct	397 ms	25176 KB	Output is correct
32	Correct	403 ms	25188 KB	Output is correct
33	Correct	378 ms	25956 KB	Output is correct
34	Correct	415 ms	26164 KB	Output is correct
35	Correct	404 ms	26568 KB	Output is correct
36	Correct	258 ms	26568 KB	Output is correct
37	Correct	357 ms	29080 KB	Output is correct
38	Correct	349 ms	29080 KB	Output is correct
39	Correct	414 ms	29080 KB	Output is correct
40	Correct	404 ms	29080 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	576 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	75 ms	35460 KB	Output is correct
12	Correct	70 ms	35588 KB	Output is correct
13	Correct	74 ms	35588 KB	Output is correct
14	Correct	91 ms	35604 KB	Output is correct
15	Correct	68 ms	37312 KB	Output is correct
16	Correct	91 ms	37312 KB	Output is correct
17	Correct	82 ms	37320 KB	Output is correct
18	Correct	77 ms	37320 KB	Output is correct
19	Correct	67 ms	37320 KB	Output is correct
20	Correct	76 ms	37320 KB	Output is correct
21	Correct	89 ms	37320 KB	Output is correct
22	Correct	118 ms	37320 KB	Output is correct
23	Correct	67 ms	37320 KB	Output is correct
24	Correct	90 ms	37320 KB	Output is correct
25	Correct	85 ms	37320 KB	Output is correct
26	Correct	59 ms	37320 KB	Output is correct
27	Correct	66 ms	37320 KB	Output is correct
28	Correct	69 ms	37320 KB	Output is correct
29	Correct	78 ms	37320 KB	Output is correct
30	Correct	81 ms	37320 KB	Output is correct
31	Correct	71 ms	37320 KB	Output is correct
32	Correct	89 ms	37320 KB	Output is correct
33	Correct	87 ms	37320 KB	Output is correct
34	Correct	57 ms	37320 KB	Output is correct
35	Correct	80 ms	37320 KB	Output is correct
36	Correct	82 ms	37320 KB	Output is correct
37	Correct	89 ms	37320 KB	Output is correct
38	Correct	96 ms	37320 KB	Output is correct
39	Correct	86 ms	37320 KB	Output is correct
40	Correct	81 ms	37320 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	480 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	576 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	266 ms	10240 KB	Output is correct
12	Correct	293 ms	11524 KB	Output is correct
13	Correct	316 ms	13068 KB	Output is correct
14	Correct	323 ms	13216 KB	Output is correct
15	Correct	311 ms	14064 KB	Output is correct
16	Correct	317 ms	14064 KB	Output is correct
17	Correct	347 ms	16892 KB	Output is correct
18	Correct	236 ms	18716 KB	Output is correct
19	Correct	265 ms	18716 KB	Output is correct
20	Correct	278 ms	18716 KB	Output is correct
21	Correct	325 ms	18716 KB	Output is correct
22	Correct	334 ms	20196 KB	Output is correct
23	Correct	374 ms	20196 KB	Output is correct
24	Correct	405 ms	20196 KB	Output is correct
25	Correct	352 ms	22624 KB	Output is correct
26	Correct	403 ms	22624 KB	Output is correct
27	Correct	397 ms	22624 KB	Output is correct
28	Correct	302 ms	25036 KB	Output is correct
29	Correct	334 ms	25036 KB	Output is correct
30	Correct	356 ms	25176 KB	Output is correct
31	Correct	397 ms	25176 KB	Output is correct
32	Correct	403 ms	25188 KB	Output is correct
33	Correct	378 ms	25956 KB	Output is correct
34	Correct	415 ms	26164 KB	Output is correct
35	Correct	404 ms	26568 KB	Output is correct
36	Correct	258 ms	26568 KB	Output is correct
37	Correct	357 ms	29080 KB	Output is correct
38	Correct	349 ms	29080 KB	Output is correct
39	Correct	414 ms	29080 KB	Output is correct
40	Correct	404 ms	29080 KB	Output is correct
41	Correct	75 ms	35460 KB	Output is correct
42	Correct	70 ms	35588 KB	Output is correct
43	Correct	74 ms	35588 KB	Output is correct
44	Correct	91 ms	35604 KB	Output is correct
45	Correct	68 ms	37312 KB	Output is correct
46	Correct	91 ms	37312 KB	Output is correct
47	Correct	82 ms	37320 KB	Output is correct
48	Correct	77 ms	37320 KB	Output is correct
49	Correct	67 ms	37320 KB	Output is correct
50	Correct	76 ms	37320 KB	Output is correct
51	Correct	89 ms	37320 KB	Output is correct
52	Correct	118 ms	37320 KB	Output is correct
53	Correct	67 ms	37320 KB	Output is correct
54	Correct	90 ms	37320 KB	Output is correct
55	Correct	85 ms	37320 KB	Output is correct
56	Correct	59 ms	37320 KB	Output is correct
57	Correct	66 ms	37320 KB	Output is correct
58	Correct	69 ms	37320 KB	Output is correct
59	Correct	78 ms	37320 KB	Output is correct
60	Correct	81 ms	37320 KB	Output is correct
61	Correct	71 ms	37320 KB	Output is correct
62	Correct	89 ms	37320 KB	Output is correct
63	Correct	87 ms	37320 KB	Output is correct
64	Correct	57 ms	37320 KB	Output is correct
65	Correct	80 ms	37320 KB	Output is correct
66	Correct	82 ms	37320 KB	Output is correct
67	Correct	89 ms	37320 KB	Output is correct
68	Correct	96 ms	37320 KB	Output is correct
69	Correct	86 ms	37320 KB	Output is correct
70	Correct	81 ms	37320 KB	Output is correct
71	Correct	604 ms	41940 KB	Output is correct
72	Correct	603 ms	42064 KB	Output is correct
73	Correct	635 ms	42064 KB	Output is correct
74	Correct	911 ms	42892 KB	Output is correct
75	Correct	573 ms	46544 KB	Output is correct
76	Correct	951 ms	46544 KB	Output is correct
77	Correct	910 ms	46544 KB	Output is correct
78	Correct	373 ms	48288 KB	Output is correct
79	Correct	486 ms	48288 KB	Output is correct
80	Correct	563 ms	49056 KB	Output is correct
81	Correct	670 ms	49056 KB	Output is correct
82	Correct	802 ms	49056 KB	Output is correct
83	Correct	563 ms	54096 KB	Output is correct
84	Correct	960 ms	54844 KB	Output is correct
85	Correct	834 ms	55060 KB	Output is correct
86	Correct	356 ms	55060 KB	Output is correct
87	Correct	506 ms	57492 KB	Output is correct
88	Correct	472 ms	57492 KB	Output is correct
89	Correct	651 ms	57492 KB	Output is correct
90	Correct	654 ms	57492 KB	Output is correct
91	Correct	580 ms	57492 KB	Output is correct
92	Runtime error	993 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.
93	Halted	0 ms	0 KB	-

답안 #80254

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 53.0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
53.0 / 53.0

Subtask #5
0 / 25.0