답안 #66976 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66976	2018-08-13T05:17:38 Z	ekrem	Snake Escaping (JOI18_snake_escaping)	C++	22 / 100	1139 ms	42012 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';
	}
	
	for(int i = 1; i <= m; i++){
		int bit = 0, say = 0, son = 0, crp = 1;
		for(int i = 1; i <= n; i++){
			scanf(" %c" ,&c);
			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 < 2; 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 ] ){
				// cout << j << " nin " << q[j].st << " si " << i << " yi kapladi cvp += " <<dp[q[j].nd] << " " << q[j].st << " , " << q[j].nd << endl;
				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:16: warning: unused variable 'say' [-Wunused-variable]
   int bit = 0, 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:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c" ,&c);
    ~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	14584 KB	Output is correct
2	Correct	56 ms	14696 KB	Output is correct
3	Correct	47 ms	14696 KB	Output is correct
4	Correct	37 ms	14696 KB	Output is correct
5	Correct	38 ms	14712 KB	Output is correct
6	Correct	36 ms	14812 KB	Output is correct
7	Correct	36 ms	14876 KB	Output is correct
8	Correct	33 ms	14876 KB	Output is correct
9	Correct	32 ms	14876 KB	Output is correct
10	Correct	32 ms	14876 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	14584 KB	Output is correct
2	Correct	56 ms	14696 KB	Output is correct
3	Correct	47 ms	14696 KB	Output is correct
4	Correct	37 ms	14696 KB	Output is correct
5	Correct	38 ms	14712 KB	Output is correct
6	Correct	36 ms	14812 KB	Output is correct
7	Correct	36 ms	14876 KB	Output is correct
8	Correct	33 ms	14876 KB	Output is correct
9	Correct	32 ms	14876 KB	Output is correct
10	Correct	32 ms	14876 KB	Output is correct
11	Correct	840 ms	30780 KB	Output is correct
12	Correct	905 ms	30780 KB	Output is correct
13	Correct	794 ms	30780 KB	Output is correct
14	Correct	805 ms	30780 KB	Output is correct
15	Correct	850 ms	30780 KB	Output is correct
16	Correct	812 ms	30780 KB	Output is correct
17	Correct	808 ms	30780 KB	Output is correct
18	Correct	793 ms	31828 KB	Output is correct
19	Correct	705 ms	31828 KB	Output is correct
20	Correct	842 ms	31828 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	14584 KB	Output is correct
2	Correct	56 ms	14696 KB	Output is correct
3	Correct	47 ms	14696 KB	Output is correct
4	Correct	37 ms	14696 KB	Output is correct
5	Correct	38 ms	14712 KB	Output is correct
6	Correct	36 ms	14812 KB	Output is correct
7	Correct	36 ms	14876 KB	Output is correct
8	Correct	33 ms	14876 KB	Output is correct
9	Correct	32 ms	14876 KB	Output is correct
10	Correct	32 ms	14876 KB	Output is correct
11	Correct	840 ms	30780 KB	Output is correct
12	Correct	905 ms	30780 KB	Output is correct
13	Correct	794 ms	30780 KB	Output is correct
14	Correct	805 ms	30780 KB	Output is correct
15	Correct	850 ms	30780 KB	Output is correct
16	Correct	812 ms	30780 KB	Output is correct
17	Correct	808 ms	30780 KB	Output is correct
18	Correct	793 ms	31828 KB	Output is correct
19	Correct	705 ms	31828 KB	Output is correct
20	Correct	842 ms	31828 KB	Output is correct
21	Correct	980 ms	31828 KB	Output is correct
22	Correct	1008 ms	34724 KB	Output is correct
23	Correct	1022 ms	34724 KB	Output is correct
24	Correct	1025 ms	34724 KB	Output is correct
25	Correct	998 ms	36228 KB	Output is correct
26	Correct	1085 ms	36228 KB	Output is correct
27	Correct	1020 ms	36228 KB	Output is correct
28	Correct	932 ms	37188 KB	Output is correct
29	Correct	934 ms	37188 KB	Output is correct
30	Correct	1010 ms	37188 KB	Output is correct
31	Correct	1050 ms	37188 KB	Output is correct
32	Correct	985 ms	37188 KB	Output is correct
33	Correct	1068 ms	37188 KB	Output is correct
34	Correct	1139 ms	41076 KB	Output is correct
35	Correct	1080 ms	41372 KB	Output is correct
36	Correct	995 ms	41372 KB	Output is correct
37	Correct	1059 ms	42012 KB	Output is correct
38	Correct	929 ms	42012 KB	Output is correct
39	Correct	979 ms	42012 KB	Output is correct
40	Correct	1071 ms	42012 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	14584 KB	Output is correct
2	Correct	56 ms	14696 KB	Output is correct
3	Correct	47 ms	14696 KB	Output is correct
4	Correct	37 ms	14696 KB	Output is correct
5	Correct	38 ms	14712 KB	Output is correct
6	Correct	36 ms	14812 KB	Output is correct
7	Correct	36 ms	14876 KB	Output is correct
8	Correct	33 ms	14876 KB	Output is correct
9	Correct	32 ms	14876 KB	Output is correct
10	Correct	32 ms	14876 KB	Output is correct
11	Incorrect	175 ms	42012 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	14584 KB	Output is correct
2	Correct	56 ms	14696 KB	Output is correct
3	Correct	47 ms	14696 KB	Output is correct
4	Correct	37 ms	14696 KB	Output is correct
5	Correct	38 ms	14712 KB	Output is correct
6	Correct	36 ms	14812 KB	Output is correct
7	Correct	36 ms	14876 KB	Output is correct
8	Correct	33 ms	14876 KB	Output is correct
9	Correct	32 ms	14876 KB	Output is correct
10	Correct	32 ms	14876 KB	Output is correct
11	Correct	840 ms	30780 KB	Output is correct
12	Correct	905 ms	30780 KB	Output is correct
13	Correct	794 ms	30780 KB	Output is correct
14	Correct	805 ms	30780 KB	Output is correct
15	Correct	850 ms	30780 KB	Output is correct
16	Correct	812 ms	30780 KB	Output is correct
17	Correct	808 ms	30780 KB	Output is correct
18	Correct	793 ms	31828 KB	Output is correct
19	Correct	705 ms	31828 KB	Output is correct
20	Correct	842 ms	31828 KB	Output is correct
21	Correct	980 ms	31828 KB	Output is correct
22	Correct	1008 ms	34724 KB	Output is correct
23	Correct	1022 ms	34724 KB	Output is correct
24	Correct	1025 ms	34724 KB	Output is correct
25	Correct	998 ms	36228 KB	Output is correct
26	Correct	1085 ms	36228 KB	Output is correct
27	Correct	1020 ms	36228 KB	Output is correct
28	Correct	932 ms	37188 KB	Output is correct
29	Correct	934 ms	37188 KB	Output is correct
30	Correct	1010 ms	37188 KB	Output is correct
31	Correct	1050 ms	37188 KB	Output is correct
32	Correct	985 ms	37188 KB	Output is correct
33	Correct	1068 ms	37188 KB	Output is correct
34	Correct	1139 ms	41076 KB	Output is correct
35	Correct	1080 ms	41372 KB	Output is correct
36	Correct	995 ms	41372 KB	Output is correct
37	Correct	1059 ms	42012 KB	Output is correct
38	Correct	929 ms	42012 KB	Output is correct
39	Correct	979 ms	42012 KB	Output is correct
40	Correct	1071 ms	42012 KB	Output is correct
41	Incorrect	175 ms	42012 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #66976

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 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
0 / 53.0

Subtask #5
0 / 25.0