답안 #67000 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67000	2018-08-13T07:55:42 Z	osmanorhan	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2000 ms	47532 KB

snake_escaping

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1600005
using namespace std;
 
int n, m, a[(1<<20)+10], dp[N], prec[N], cvp[1000005], kaps[3000][200];
char c;
pair < int , int > q[1000005];
 
int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
 
	for(int i = 0; i < 1594323; i++){
		int x = i, crp = 1, ckr = -1, say = 0, bit = 0;
		while(x){
			if(x%3 == 2){
				ckr = crp;
				break;
			}
			bit += (1<<say)*(x%3);
			say++;
			crp *= 3;
			x /= 3;
		}
		if(ckr == -1)
			prec[i] = -bit;
		else
			prec[i] = ckr;
	}
 
	scanf("%d %d",&n ,&m);
 
	for(int i = 0; i < (1<<n); i++){
		scanf(" %c",&c);
		a[i] = c - '0';
	}
	char s[30];
	for(int i = 1; i <= m; i++){
		int say = 0, son = 0, crp = 1;
		long long bit = 0;
      scanf(" %s",s);
		for(int i = 1; i <= n; i++){
			c = s[i-1];
			bit *= 3;
			bit += (c == '?') ? 2 : c - '0';
		}
		for(int say = 1; say <= 13; say++){
			son += crp*(bit%3);
			crp *= 3;
			bit/=3;
		}
		// cout << bit << " , " << son << endl;
		q[i] = mp(bit, son);
	}
 
	for(int i = 0; i < 2187; i++)
		for(int j = 0; j < (1<<7); j++){
			if(i == 0 and j == 0)
				kaps[i][j] = 1;
			else if(i%3 != 2 and i%3 != j%2)
				kaps[i][j] = 0;
			else
				kaps[i][j] = kaps[i/3][j/2];
		}
 
	for(int i = 0; i < (1<<7); i++){
 
		for(int j = 0; j < 1594323; j++){
			if(prec[j] <= 0)
				dp[j] = a[i*(1<<13) - prec[j]];
			else
				dp[j] = dp[j - prec[j]] + dp[j - prec[j]*2];
		}
 
		for(int j = 1; j <= m; j++){
			if(kaps[q[j].st ][i ] ){
				cvp[j] += dp[q[j].nd];
			}
		}
	}
	for(int i = 1; i <= m; i++)
		printf("%d\n",cvp[i]);
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:43:7: warning: unused variable 'say' [-Wunused-variable]
   int say = 0, son = 0, crp = 1;
       ^~~
snake_escaping.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
   ~~~~~^~~~~~~~~~
snake_escaping.cpp:45:12: 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	398 ms	14712 KB	Output is correct
2	Correct	426 ms	14712 KB	Output is correct
3	Correct	425 ms	14720 KB	Output is correct
4	Correct	397 ms	14828 KB	Output is correct
5	Correct	494 ms	14948 KB	Output is correct
6	Correct	424 ms	14948 KB	Output is correct
7	Correct	424 ms	14948 KB	Output is correct
8	Correct	399 ms	14948 KB	Output is correct
9	Correct	422 ms	14948 KB	Output is correct
10	Correct	415 ms	14948 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	14712 KB	Output is correct
2	Correct	426 ms	14712 KB	Output is correct
3	Correct	425 ms	14720 KB	Output is correct
4	Correct	397 ms	14828 KB	Output is correct
5	Correct	494 ms	14948 KB	Output is correct
6	Correct	424 ms	14948 KB	Output is correct
7	Correct	424 ms	14948 KB	Output is correct
8	Correct	399 ms	14948 KB	Output is correct
9	Correct	422 ms	14948 KB	Output is correct
10	Correct	415 ms	14948 KB	Output is correct
11	Correct	1002 ms	30444 KB	Output is correct
12	Correct	1049 ms	30444 KB	Output is correct
13	Correct	967 ms	30444 KB	Output is correct
14	Correct	952 ms	30444 KB	Output is correct
15	Correct	943 ms	30456 KB	Output is correct
16	Correct	905 ms	30456 KB	Output is correct
17	Correct	932 ms	30456 KB	Output is correct
18	Correct	925 ms	31516 KB	Output is correct
19	Correct	830 ms	31516 KB	Output is correct
20	Correct	1063 ms	31516 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	14712 KB	Output is correct
2	Correct	426 ms	14712 KB	Output is correct
3	Correct	425 ms	14720 KB	Output is correct
4	Correct	397 ms	14828 KB	Output is correct
5	Correct	494 ms	14948 KB	Output is correct
6	Correct	424 ms	14948 KB	Output is correct
7	Correct	424 ms	14948 KB	Output is correct
8	Correct	399 ms	14948 KB	Output is correct
9	Correct	422 ms	14948 KB	Output is correct
10	Correct	415 ms	14948 KB	Output is correct
11	Correct	1002 ms	30444 KB	Output is correct
12	Correct	1049 ms	30444 KB	Output is correct
13	Correct	967 ms	30444 KB	Output is correct
14	Correct	952 ms	30444 KB	Output is correct
15	Correct	943 ms	30456 KB	Output is correct
16	Correct	905 ms	30456 KB	Output is correct
17	Correct	932 ms	30456 KB	Output is correct
18	Correct	925 ms	31516 KB	Output is correct
19	Correct	830 ms	31516 KB	Output is correct
20	Correct	1063 ms	31516 KB	Output is correct
21	Correct	1173 ms	31516 KB	Output is correct
22	Correct	1034 ms	32172 KB	Output is correct
23	Correct	897 ms	33580 KB	Output is correct
24	Correct	948 ms	33580 KB	Output is correct
25	Correct	930 ms	35392 KB	Output is correct
26	Correct	970 ms	35392 KB	Output is correct
27	Correct	926 ms	35392 KB	Output is correct
28	Correct	924 ms	36288 KB	Output is correct
29	Correct	976 ms	36288 KB	Output is correct
30	Correct	946 ms	36288 KB	Output is correct
31	Correct	1074 ms	36288 KB	Output is correct
32	Correct	1008 ms	38092 KB	Output is correct
33	Correct	860 ms	41260 KB	Output is correct
34	Correct	1089 ms	41344 KB	Output is correct
35	Correct	1043 ms	41732 KB	Output is correct
36	Correct	947 ms	41732 KB	Output is correct
37	Correct	1046 ms	42304 KB	Output is correct
38	Correct	967 ms	42304 KB	Output is correct
39	Correct	1010 ms	42304 KB	Output is correct
40	Correct	1047 ms	42304 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	14712 KB	Output is correct
2	Correct	426 ms	14712 KB	Output is correct
3	Correct	425 ms	14720 KB	Output is correct
4	Correct	397 ms	14828 KB	Output is correct
5	Correct	494 ms	14948 KB	Output is correct
6	Correct	424 ms	14948 KB	Output is correct
7	Correct	424 ms	14948 KB	Output is correct
8	Correct	399 ms	14948 KB	Output is correct
9	Correct	422 ms	14948 KB	Output is correct
10	Correct	415 ms	14948 KB	Output is correct
11	Correct	577 ms	42304 KB	Output is correct
12	Correct	629 ms	42304 KB	Output is correct
13	Correct	600 ms	42304 KB	Output is correct
14	Correct	539 ms	42304 KB	Output is correct
15	Correct	594 ms	42304 KB	Output is correct
16	Correct	580 ms	42304 KB	Output is correct
17	Correct	521 ms	42304 KB	Output is correct
18	Correct	500 ms	42304 KB	Output is correct
19	Correct	472 ms	42304 KB	Output is correct
20	Correct	601 ms	42304 KB	Output is correct
21	Correct	619 ms	42304 KB	Output is correct
22	Correct	585 ms	42304 KB	Output is correct
23	Correct	548 ms	42304 KB	Output is correct
24	Correct	546 ms	42304 KB	Output is correct
25	Correct	533 ms	42304 KB	Output is correct
26	Correct	508 ms	42304 KB	Output is correct
27	Correct	583 ms	42304 KB	Output is correct
28	Correct	514 ms	42304 KB	Output is correct
29	Correct	580 ms	42304 KB	Output is correct
30	Correct	566 ms	42304 KB	Output is correct
31	Correct	563 ms	42304 KB	Output is correct
32	Correct	565 ms	42304 KB	Output is correct
33	Correct	578 ms	42304 KB	Output is correct
34	Correct	655 ms	42304 KB	Output is correct
35	Correct	601 ms	42304 KB	Output is correct
36	Correct	727 ms	42304 KB	Output is correct
37	Correct	603 ms	42304 KB	Output is correct
38	Correct	582 ms	42304 KB	Output is correct
39	Correct	571 ms	42304 KB	Output is correct
40	Correct	603 ms	42304 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	14712 KB	Output is correct
2	Correct	426 ms	14712 KB	Output is correct
3	Correct	425 ms	14720 KB	Output is correct
4	Correct	397 ms	14828 KB	Output is correct
5	Correct	494 ms	14948 KB	Output is correct
6	Correct	424 ms	14948 KB	Output is correct
7	Correct	424 ms	14948 KB	Output is correct
8	Correct	399 ms	14948 KB	Output is correct
9	Correct	422 ms	14948 KB	Output is correct
10	Correct	415 ms	14948 KB	Output is correct
11	Correct	1002 ms	30444 KB	Output is correct
12	Correct	1049 ms	30444 KB	Output is correct
13	Correct	967 ms	30444 KB	Output is correct
14	Correct	952 ms	30444 KB	Output is correct
15	Correct	943 ms	30456 KB	Output is correct
16	Correct	905 ms	30456 KB	Output is correct
17	Correct	932 ms	30456 KB	Output is correct
18	Correct	925 ms	31516 KB	Output is correct
19	Correct	830 ms	31516 KB	Output is correct
20	Correct	1063 ms	31516 KB	Output is correct
21	Correct	1173 ms	31516 KB	Output is correct
22	Correct	1034 ms	32172 KB	Output is correct
23	Correct	897 ms	33580 KB	Output is correct
24	Correct	948 ms	33580 KB	Output is correct
25	Correct	930 ms	35392 KB	Output is correct
26	Correct	970 ms	35392 KB	Output is correct
27	Correct	926 ms	35392 KB	Output is correct
28	Correct	924 ms	36288 KB	Output is correct
29	Correct	976 ms	36288 KB	Output is correct
30	Correct	946 ms	36288 KB	Output is correct
31	Correct	1074 ms	36288 KB	Output is correct
32	Correct	1008 ms	38092 KB	Output is correct
33	Correct	860 ms	41260 KB	Output is correct
34	Correct	1089 ms	41344 KB	Output is correct
35	Correct	1043 ms	41732 KB	Output is correct
36	Correct	947 ms	41732 KB	Output is correct
37	Correct	1046 ms	42304 KB	Output is correct
38	Correct	967 ms	42304 KB	Output is correct
39	Correct	1010 ms	42304 KB	Output is correct
40	Correct	1047 ms	42304 KB	Output is correct
41	Correct	577 ms	42304 KB	Output is correct
42	Correct	629 ms	42304 KB	Output is correct
43	Correct	600 ms	42304 KB	Output is correct
44	Correct	539 ms	42304 KB	Output is correct
45	Correct	594 ms	42304 KB	Output is correct
46	Correct	580 ms	42304 KB	Output is correct
47	Correct	521 ms	42304 KB	Output is correct
48	Correct	500 ms	42304 KB	Output is correct
49	Correct	472 ms	42304 KB	Output is correct
50	Correct	601 ms	42304 KB	Output is correct
51	Correct	619 ms	42304 KB	Output is correct
52	Correct	585 ms	42304 KB	Output is correct
53	Correct	548 ms	42304 KB	Output is correct
54	Correct	546 ms	42304 KB	Output is correct
55	Correct	533 ms	42304 KB	Output is correct
56	Correct	508 ms	42304 KB	Output is correct
57	Correct	583 ms	42304 KB	Output is correct
58	Correct	514 ms	42304 KB	Output is correct
59	Correct	580 ms	42304 KB	Output is correct
60	Correct	566 ms	42304 KB	Output is correct
61	Correct	563 ms	42304 KB	Output is correct
62	Correct	565 ms	42304 KB	Output is correct
63	Correct	578 ms	42304 KB	Output is correct
64	Correct	655 ms	42304 KB	Output is correct
65	Correct	601 ms	42304 KB	Output is correct
66	Correct	727 ms	42304 KB	Output is correct
67	Correct	603 ms	42304 KB	Output is correct
68	Correct	582 ms	42304 KB	Output is correct
69	Correct	571 ms	42304 KB	Output is correct
70	Correct	603 ms	42304 KB	Output is correct
71	Correct	1581 ms	47532 KB	Output is correct
72	Correct	1672 ms	47532 KB	Output is correct
73	Correct	1679 ms	47532 KB	Output is correct
74	Correct	1907 ms	47532 KB	Output is correct
75	Execution timed out	2067 ms	47532 KB	Time limit exceeded
76	Halted	0 ms	0 KB	-

답안 #67000

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