답안 #64581 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64581	2018-08-05T00:16:43 Z	keko37	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2000 ms	38680 KB

snake_escaping

#include<iostream>

using namespace std;

const int MAXN = (1<<20) + 10;

int n, q, a, b, c, sol, mask, N, rev, count, i, j, tc;
char l[30], cc;
int val[MAXN], sum0[MAXN], sum1[MAXN], pc[MAXN];

void precompute () {
	for (i=0; i<(1<<n); i++) {
		pc[i] = __builtin_popcount(i);
		sum0[i] = val[i];
		sum1[i] = val[i ^ ((1<<n) - 1)];
	}
	for (i=0; i<n; i++) {
		for (j=0; j<(1<<n); j++) {
			if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)];
			if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)];
		}
	}
}
  #define pcc(x) putchar(x);
    
int main () {
	cin >> n >> q;
	do {
		cc = getchar();
	} while (!(cc>='0' && cc<='9'));
	for (i=0; i<(1<<n); i++) {
		if (i>0) {
			cc = getchar();
		}
		val[i] = cc - '0';
	}
	precompute();
	for (tc=0; tc<q; tc++) {
		a = b = c = 0;
		do {
			cc = getchar();
		} while (!(cc=='0' || cc=='1' || cc=='?'));
		for (i=0; i<n; i++) {
			if (i>0) cc = getchar();
			l[i] = cc;
			if (l[i] == '?') {
				a ^= (1<<(n-1-i));
			} else if (l[i] == '0') {
				b ^= (1<<(n-1-i));
			} else {
				c ^= (1<<(n-1-i));
			}
		}
		sol = 0, mask = 0;
		if (pc[a] <= n/3) {
			do {
				sol += val[mask | c];
			} while (mask = (mask-a) & a);
		} else if (pc[b] <= n/3) {
			do {
				if (pc[mask | a] & 1) {
					sol -= sum1[mask | a];
				} else {
					sol += sum1[mask | a];
				}
			} while (mask = (mask-b) & b);
			if (sol < 0) sol = -sol;
		} else {
			do {
				if (pc[mask | a] & 1) {
					sol -= sum0[mask | a];
				} else {
					sol += sum0[mask | a];
				}
			} while (mask = (mask-c) & c);
			if (sol < 0) sol = -sol;
		}

        N = sol, rev, count = 0;
        rev = N;
        if (N == 0) { pcc('0'); putchar('\n'); continue ;}
        while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
        rev = 0;
        while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}  //store reverse of N in rev
        while (rev != 0) { pcc(rev % 10 + '0'); rev /= 10;}
        while (count--) pcc('0');
		putchar('\n');
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:58:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-a) & a);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:66:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-b) & b);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:75:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-c) & c);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:79:31: warning: right operand of comma operator has no effect [-Wunused-value]
         N = sol, rev, count = 0;
                               ^

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	335 ms	4648 KB	Output is correct
12	Correct	323 ms	4648 KB	Output is correct
13	Correct	346 ms	4648 KB	Output is correct
14	Correct	333 ms	4648 KB	Output is correct
15	Correct	396 ms	4684 KB	Output is correct
16	Correct	338 ms	4684 KB	Output is correct
17	Correct	356 ms	4684 KB	Output is correct
18	Correct	250 ms	5632 KB	Output is correct
19	Correct	256 ms	5632 KB	Output is correct
20	Correct	312 ms	5632 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	335 ms	4648 KB	Output is correct
12	Correct	323 ms	4648 KB	Output is correct
13	Correct	346 ms	4648 KB	Output is correct
14	Correct	333 ms	4648 KB	Output is correct
15	Correct	396 ms	4684 KB	Output is correct
16	Correct	338 ms	4684 KB	Output is correct
17	Correct	356 ms	4684 KB	Output is correct
18	Correct	250 ms	5632 KB	Output is correct
19	Correct	256 ms	5632 KB	Output is correct
20	Correct	312 ms	5632 KB	Output is correct
21	Correct	347 ms	5632 KB	Output is correct
22	Correct	387 ms	5632 KB	Output is correct
23	Correct	375 ms	5632 KB	Output is correct
24	Correct	408 ms	5632 KB	Output is correct
25	Correct	422 ms	5804 KB	Output is correct
26	Correct	408 ms	5804 KB	Output is correct
27	Correct	425 ms	5804 KB	Output is correct
28	Correct	342 ms	6760 KB	Output is correct
29	Correct	323 ms	6760 KB	Output is correct
30	Correct	478 ms	6760 KB	Output is correct
31	Correct	469 ms	6760 KB	Output is correct
32	Correct	538 ms	6760 KB	Output is correct
33	Correct	357 ms	6760 KB	Output is correct
34	Correct	430 ms	6760 KB	Output is correct
35	Correct	476 ms	6760 KB	Output is correct
36	Correct	318 ms	6760 KB	Output is correct
37	Correct	445 ms	6760 KB	Output is correct
38	Correct	346 ms	6760 KB	Output is correct
39	Correct	391 ms	6760 KB	Output is correct
40	Correct	440 ms	6760 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	133 ms	17252 KB	Output is correct
12	Correct	129 ms	17252 KB	Output is correct
13	Correct	133 ms	17340 KB	Output is correct
14	Correct	193 ms	17340 KB	Output is correct
15	Correct	154 ms	17340 KB	Output is correct
16	Correct	200 ms	17340 KB	Output is correct
17	Correct	166 ms	17340 KB	Output is correct
18	Correct	113 ms	17376 KB	Output is correct
19	Correct	116 ms	17376 KB	Output is correct
20	Correct	128 ms	17376 KB	Output is correct
21	Correct	183 ms	17376 KB	Output is correct
22	Correct	208 ms	17376 KB	Output is correct
23	Correct	117 ms	17376 KB	Output is correct
24	Correct	142 ms	17376 KB	Output is correct
25	Correct	181 ms	17376 KB	Output is correct
26	Correct	92 ms	17376 KB	Output is correct
27	Correct	109 ms	17376 KB	Output is correct
28	Correct	102 ms	17376 KB	Output is correct
29	Correct	126 ms	17376 KB	Output is correct
30	Correct	148 ms	17376 KB	Output is correct
31	Correct	114 ms	17376 KB	Output is correct
32	Correct	162 ms	17376 KB	Output is correct
33	Correct	160 ms	17384 KB	Output is correct
34	Correct	106 ms	17384 KB	Output is correct
35	Correct	131 ms	17384 KB	Output is correct
36	Correct	136 ms	17384 KB	Output is correct
37	Correct	155 ms	17384 KB	Output is correct
38	Correct	142 ms	17384 KB	Output is correct
39	Correct	144 ms	17384 KB	Output is correct
40	Correct	136 ms	17384 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	335 ms	4648 KB	Output is correct
12	Correct	323 ms	4648 KB	Output is correct
13	Correct	346 ms	4648 KB	Output is correct
14	Correct	333 ms	4648 KB	Output is correct
15	Correct	396 ms	4684 KB	Output is correct
16	Correct	338 ms	4684 KB	Output is correct
17	Correct	356 ms	4684 KB	Output is correct
18	Correct	250 ms	5632 KB	Output is correct
19	Correct	256 ms	5632 KB	Output is correct
20	Correct	312 ms	5632 KB	Output is correct
21	Correct	347 ms	5632 KB	Output is correct
22	Correct	387 ms	5632 KB	Output is correct
23	Correct	375 ms	5632 KB	Output is correct
24	Correct	408 ms	5632 KB	Output is correct
25	Correct	422 ms	5804 KB	Output is correct
26	Correct	408 ms	5804 KB	Output is correct
27	Correct	425 ms	5804 KB	Output is correct
28	Correct	342 ms	6760 KB	Output is correct
29	Correct	323 ms	6760 KB	Output is correct
30	Correct	478 ms	6760 KB	Output is correct
31	Correct	469 ms	6760 KB	Output is correct
32	Correct	538 ms	6760 KB	Output is correct
33	Correct	357 ms	6760 KB	Output is correct
34	Correct	430 ms	6760 KB	Output is correct
35	Correct	476 ms	6760 KB	Output is correct
36	Correct	318 ms	6760 KB	Output is correct
37	Correct	445 ms	6760 KB	Output is correct
38	Correct	346 ms	6760 KB	Output is correct
39	Correct	391 ms	6760 KB	Output is correct
40	Correct	440 ms	6760 KB	Output is correct
41	Correct	133 ms	17252 KB	Output is correct
42	Correct	129 ms	17252 KB	Output is correct
43	Correct	133 ms	17340 KB	Output is correct
44	Correct	193 ms	17340 KB	Output is correct
45	Correct	154 ms	17340 KB	Output is correct
46	Correct	200 ms	17340 KB	Output is correct
47	Correct	166 ms	17340 KB	Output is correct
48	Correct	113 ms	17376 KB	Output is correct
49	Correct	116 ms	17376 KB	Output is correct
50	Correct	128 ms	17376 KB	Output is correct
51	Correct	183 ms	17376 KB	Output is correct
52	Correct	208 ms	17376 KB	Output is correct
53	Correct	117 ms	17376 KB	Output is correct
54	Correct	142 ms	17376 KB	Output is correct
55	Correct	181 ms	17376 KB	Output is correct
56	Correct	92 ms	17376 KB	Output is correct
57	Correct	109 ms	17376 KB	Output is correct
58	Correct	102 ms	17376 KB	Output is correct
59	Correct	126 ms	17376 KB	Output is correct
60	Correct	148 ms	17376 KB	Output is correct
61	Correct	114 ms	17376 KB	Output is correct
62	Correct	162 ms	17376 KB	Output is correct
63	Correct	160 ms	17384 KB	Output is correct
64	Correct	106 ms	17384 KB	Output is correct
65	Correct	131 ms	17384 KB	Output is correct
66	Correct	136 ms	17384 KB	Output is correct
67	Correct	155 ms	17384 KB	Output is correct
68	Correct	142 ms	17384 KB	Output is correct
69	Correct	144 ms	17384 KB	Output is correct
70	Correct	136 ms	17384 KB	Output is correct
71	Correct	787 ms	21976 KB	Output is correct
72	Correct	872 ms	22020 KB	Output is correct
73	Correct	1012 ms	22020 KB	Output is correct
74	Execution timed out	2045 ms	38680 KB	Time limit exceeded
75	Halted	0 ms	0 KB	-

답안 #64581

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