답안 #58958 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58958	2018-07-19T21:33:06 Z	TadijaSebez	Snake Escaping (JOI18_snake_escaping)	C++11	75 / 100	1548 ms	66560 KB

snake_escaping

#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[((1<<n)-1)^i]=s[i]-'0';
	}
	for(i=0;i<n;i++)
	{
		for(mask=0;mask<(1<<n);mask++)
		{
			if((mask>>i)&1)
			{
				dp1[mask]+=dp1[mask^(1<<i)];
				dp0[mask]+=dp0[mask^(1<<i)];
			}
		}
	}
	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);
				if((pc[mask]&1)==(pc[a]&1)) ans+=dp0[mask|c];
				else ans-=dp0[mask|c];
				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

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",t);
   ~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4436 KB	Output is correct
2	Correct	10 ms	4552 KB	Output is correct
3	Correct	7 ms	4552 KB	Output is correct
4	Correct	7 ms	4552 KB	Output is correct
5	Correct	8 ms	4628 KB	Output is correct
6	Correct	7 ms	4628 KB	Output is correct
7	Correct	7 ms	4680 KB	Output is correct
8	Correct	7 ms	4680 KB	Output is correct
9	Correct	8 ms	4680 KB	Output is correct
10	Correct	9 ms	4680 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4436 KB	Output is correct
2	Correct	10 ms	4552 KB	Output is correct
3	Correct	7 ms	4552 KB	Output is correct
4	Correct	7 ms	4552 KB	Output is correct
5	Correct	8 ms	4628 KB	Output is correct
6	Correct	7 ms	4628 KB	Output is correct
7	Correct	7 ms	4680 KB	Output is correct
8	Correct	7 ms	4680 KB	Output is correct
9	Correct	8 ms	4680 KB	Output is correct
10	Correct	9 ms	4680 KB	Output is correct
11	Correct	388 ms	8656 KB	Output is correct
12	Correct	339 ms	8656 KB	Output is correct
13	Correct	374 ms	8656 KB	Output is correct
14	Correct	374 ms	8656 KB	Output is correct
15	Correct	451 ms	8704 KB	Output is correct
16	Correct	347 ms	8704 KB	Output is correct
17	Correct	329 ms	8704 KB	Output is correct
18	Correct	236 ms	9600 KB	Output is correct
19	Correct	303 ms	9600 KB	Output is correct
20	Correct	351 ms	9600 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4436 KB	Output is correct
2	Correct	10 ms	4552 KB	Output is correct
3	Correct	7 ms	4552 KB	Output is correct
4	Correct	7 ms	4552 KB	Output is correct
5	Correct	8 ms	4628 KB	Output is correct
6	Correct	7 ms	4628 KB	Output is correct
7	Correct	7 ms	4680 KB	Output is correct
8	Correct	7 ms	4680 KB	Output is correct
9	Correct	8 ms	4680 KB	Output is correct
10	Correct	9 ms	4680 KB	Output is correct
11	Correct	388 ms	8656 KB	Output is correct
12	Correct	339 ms	8656 KB	Output is correct
13	Correct	374 ms	8656 KB	Output is correct
14	Correct	374 ms	8656 KB	Output is correct
15	Correct	451 ms	8704 KB	Output is correct
16	Correct	347 ms	8704 KB	Output is correct
17	Correct	329 ms	8704 KB	Output is correct
18	Correct	236 ms	9600 KB	Output is correct
19	Correct	303 ms	9600 KB	Output is correct
20	Correct	351 ms	9600 KB	Output is correct
21	Correct	382 ms	9600 KB	Output is correct
22	Correct	397 ms	9600 KB	Output is correct
23	Correct	394 ms	9600 KB	Output is correct
24	Correct	415 ms	9600 KB	Output is correct
25	Correct	380 ms	9780 KB	Output is correct
26	Correct	448 ms	9780 KB	Output is correct
27	Correct	430 ms	9780 KB	Output is correct
28	Correct	298 ms	10796 KB	Output is correct
29	Correct	371 ms	10796 KB	Output is correct
30	Correct	401 ms	10796 KB	Output is correct
31	Correct	387 ms	10796 KB	Output is correct
32	Correct	403 ms	10796 KB	Output is correct
33	Correct	386 ms	10796 KB	Output is correct
34	Correct	519 ms	10796 KB	Output is correct
35	Correct	468 ms	10796 KB	Output is correct
36	Correct	284 ms	10796 KB	Output is correct
37	Correct	356 ms	10796 KB	Output is correct
38	Correct	392 ms	10796 KB	Output is correct
39	Correct	462 ms	10796 KB	Output is correct
40	Correct	472 ms	10796 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4436 KB	Output is correct
2	Correct	10 ms	4552 KB	Output is correct
3	Correct	7 ms	4552 KB	Output is correct
4	Correct	7 ms	4552 KB	Output is correct
5	Correct	8 ms	4628 KB	Output is correct
6	Correct	7 ms	4628 KB	Output is correct
7	Correct	7 ms	4680 KB	Output is correct
8	Correct	7 ms	4680 KB	Output is correct
9	Correct	8 ms	4680 KB	Output is correct
10	Correct	9 ms	4680 KB	Output is correct
11	Correct	87 ms	14124 KB	Output is correct
12	Correct	83 ms	14124 KB	Output is correct
13	Correct	132 ms	14140 KB	Output is correct
14	Correct	111 ms	14220 KB	Output is correct
15	Correct	82 ms	14296 KB	Output is correct
16	Correct	125 ms	14296 KB	Output is correct
17	Correct	133 ms	14296 KB	Output is correct
18	Correct	75 ms	14396 KB	Output is correct
19	Correct	82 ms	14396 KB	Output is correct
20	Correct	96 ms	14396 KB	Output is correct
21	Correct	109 ms	14396 KB	Output is correct
22	Correct	155 ms	14396 KB	Output is correct
23	Correct	87 ms	14396 KB	Output is correct
24	Correct	120 ms	14396 KB	Output is correct
25	Correct	158 ms	14396 KB	Output is correct
26	Correct	70 ms	14396 KB	Output is correct
27	Correct	93 ms	14396 KB	Output is correct
28	Correct	103 ms	14396 KB	Output is correct
29	Correct	95 ms	14396 KB	Output is correct
30	Correct	90 ms	14396 KB	Output is correct
31	Correct	84 ms	14396 KB	Output is correct
32	Correct	141 ms	14396 KB	Output is correct
33	Correct	125 ms	14396 KB	Output is correct
34	Correct	75 ms	14396 KB	Output is correct
35	Correct	105 ms	14396 KB	Output is correct
36	Correct	116 ms	14396 KB	Output is correct
37	Correct	110 ms	14396 KB	Output is correct
38	Correct	104 ms	14396 KB	Output is correct
39	Correct	126 ms	14396 KB	Output is correct
40	Correct	107 ms	14396 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4436 KB	Output is correct
2	Correct	10 ms	4552 KB	Output is correct
3	Correct	7 ms	4552 KB	Output is correct
4	Correct	7 ms	4552 KB	Output is correct
5	Correct	8 ms	4628 KB	Output is correct
6	Correct	7 ms	4628 KB	Output is correct
7	Correct	7 ms	4680 KB	Output is correct
8	Correct	7 ms	4680 KB	Output is correct
9	Correct	8 ms	4680 KB	Output is correct
10	Correct	9 ms	4680 KB	Output is correct
11	Correct	388 ms	8656 KB	Output is correct
12	Correct	339 ms	8656 KB	Output is correct
13	Correct	374 ms	8656 KB	Output is correct
14	Correct	374 ms	8656 KB	Output is correct
15	Correct	451 ms	8704 KB	Output is correct
16	Correct	347 ms	8704 KB	Output is correct
17	Correct	329 ms	8704 KB	Output is correct
18	Correct	236 ms	9600 KB	Output is correct
19	Correct	303 ms	9600 KB	Output is correct
20	Correct	351 ms	9600 KB	Output is correct
21	Correct	382 ms	9600 KB	Output is correct
22	Correct	397 ms	9600 KB	Output is correct
23	Correct	394 ms	9600 KB	Output is correct
24	Correct	415 ms	9600 KB	Output is correct
25	Correct	380 ms	9780 KB	Output is correct
26	Correct	448 ms	9780 KB	Output is correct
27	Correct	430 ms	9780 KB	Output is correct
28	Correct	298 ms	10796 KB	Output is correct
29	Correct	371 ms	10796 KB	Output is correct
30	Correct	401 ms	10796 KB	Output is correct
31	Correct	387 ms	10796 KB	Output is correct
32	Correct	403 ms	10796 KB	Output is correct
33	Correct	386 ms	10796 KB	Output is correct
34	Correct	519 ms	10796 KB	Output is correct
35	Correct	468 ms	10796 KB	Output is correct
36	Correct	284 ms	10796 KB	Output is correct
37	Correct	356 ms	10796 KB	Output is correct
38	Correct	392 ms	10796 KB	Output is correct
39	Correct	462 ms	10796 KB	Output is correct
40	Correct	472 ms	10796 KB	Output is correct
41	Correct	87 ms	14124 KB	Output is correct
42	Correct	83 ms	14124 KB	Output is correct
43	Correct	132 ms	14140 KB	Output is correct
44	Correct	111 ms	14220 KB	Output is correct
45	Correct	82 ms	14296 KB	Output is correct
46	Correct	125 ms	14296 KB	Output is correct
47	Correct	133 ms	14296 KB	Output is correct
48	Correct	75 ms	14396 KB	Output is correct
49	Correct	82 ms	14396 KB	Output is correct
50	Correct	96 ms	14396 KB	Output is correct
51	Correct	109 ms	14396 KB	Output is correct
52	Correct	155 ms	14396 KB	Output is correct
53	Correct	87 ms	14396 KB	Output is correct
54	Correct	120 ms	14396 KB	Output is correct
55	Correct	158 ms	14396 KB	Output is correct
56	Correct	70 ms	14396 KB	Output is correct
57	Correct	93 ms	14396 KB	Output is correct
58	Correct	103 ms	14396 KB	Output is correct
59	Correct	95 ms	14396 KB	Output is correct
60	Correct	90 ms	14396 KB	Output is correct
61	Correct	84 ms	14396 KB	Output is correct
62	Correct	141 ms	14396 KB	Output is correct
63	Correct	125 ms	14396 KB	Output is correct
64	Correct	75 ms	14396 KB	Output is correct
65	Correct	105 ms	14396 KB	Output is correct
66	Correct	116 ms	14396 KB	Output is correct
67	Correct	110 ms	14396 KB	Output is correct
68	Correct	104 ms	14396 KB	Output is correct
69	Correct	126 ms	14396 KB	Output is correct
70	Correct	107 ms	14396 KB	Output is correct
71	Correct	712 ms	18996 KB	Output is correct
72	Correct	731 ms	19372 KB	Output is correct
73	Correct	946 ms	19372 KB	Output is correct
74	Correct	1096 ms	19372 KB	Output is correct
75	Correct	654 ms	40240 KB	Output is correct
76	Correct	1548 ms	40240 KB	Output is correct
77	Correct	1077 ms	40240 KB	Output is correct
78	Correct	351 ms	42244 KB	Output is correct
79	Correct	723 ms	58068 KB	Output is correct
80	Runtime error	770 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.
81	Halted	0 ms	0 KB	-

답안 #58958

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