답안 #64572 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64572	2018-08-04T23:44:14 Z	keko37	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	454 ms	66560 KB

snake_escaping

#include<iostream>

using namespace std;

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

int n, q, a, b, c, sol, mask;
char l[30], cc;
int val[MAXN], sum0[MAXN], sum1[MAXN], pc[MAXN];

void precompute () {
	for (int i=0; i<(1<<n); i++) {
		pc[i] = __builtin_popcount(i);
		sum0[i] = val[i];
		sum1[i] = val[i ^ ((1<<n) - 1)];
	}
	for (int i=0; i<n; i++) {
		for (int 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_unlocked(x);
    inline void writeInt (int n)
    {
        int N = n, rev, count = 0;
        rev = N;
        if (N == 0) { pcc('0'); pcc('\n'); return ;}
        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');
    }
    
int main () {
	cin >> n >> q;
	for (int i=0; i<(1<<n); i++) {
		do {
			cc = getchar();
		} while (!((cc>='0' && cc<='9') || cc=='?'));
		val[i] = cc - '0';
	}
	precompute();
	for (int tc=0; tc<q; tc++) {
		a = b = c = 0;
		for (int i=0; i<n; i++) {
			do {
				cc = getchar();
			} while (!((cc>='0' && cc<='9') || cc=='?'));
			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;
		}
		writeInt(sol);
		putchar('\n');	
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:65:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-a) & a);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:73:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-b) & b);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:82:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-c) & c);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	660 KB	Output is correct
10	Correct	3 ms	788 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	660 KB	Output is correct
10	Correct	3 ms	788 KB	Output is correct
11	Correct	273 ms	6524 KB	Output is correct
12	Correct	279 ms	6524 KB	Output is correct
13	Correct	246 ms	6524 KB	Output is correct
14	Correct	297 ms	6524 KB	Output is correct
15	Correct	254 ms	6872 KB	Output is correct
16	Correct	262 ms	6872 KB	Output is correct
17	Correct	266 ms	6872 KB	Output is correct
18	Correct	191 ms	8576 KB	Output is correct
19	Correct	224 ms	8576 KB	Output is correct
20	Correct	265 ms	8576 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	660 KB	Output is correct
10	Correct	3 ms	788 KB	Output is correct
11	Correct	273 ms	6524 KB	Output is correct
12	Correct	279 ms	6524 KB	Output is correct
13	Correct	246 ms	6524 KB	Output is correct
14	Correct	297 ms	6524 KB	Output is correct
15	Correct	254 ms	6872 KB	Output is correct
16	Correct	262 ms	6872 KB	Output is correct
17	Correct	266 ms	6872 KB	Output is correct
18	Correct	191 ms	8576 KB	Output is correct
19	Correct	224 ms	8576 KB	Output is correct
20	Correct	265 ms	8576 KB	Output is correct
21	Correct	313 ms	8576 KB	Output is correct
22	Correct	336 ms	8576 KB	Output is correct
23	Correct	416 ms	8576 KB	Output is correct
24	Correct	392 ms	8576 KB	Output is correct
25	Correct	398 ms	8824 KB	Output is correct
26	Correct	382 ms	8824 KB	Output is correct
27	Correct	427 ms	8824 KB	Output is correct
28	Correct	245 ms	9692 KB	Output is correct
29	Correct	273 ms	9692 KB	Output is correct
30	Correct	317 ms	9692 KB	Output is correct
31	Correct	346 ms	9692 KB	Output is correct
32	Correct	454 ms	9692 KB	Output is correct
33	Correct	265 ms	9692 KB	Output is correct
34	Correct	321 ms	9692 KB	Output is correct
35	Correct	372 ms	21816 KB	Output is correct
36	Correct	225 ms	34012 KB	Output is correct
37	Correct	277 ms	49800 KB	Output is correct
38	Correct	273 ms	61628 KB	Output is correct
39	Runtime error	360 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.
40	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	660 KB	Output is correct
10	Correct	3 ms	788 KB	Output is correct
11	Runtime error	106 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.
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	660 KB	Output is correct
10	Correct	3 ms	788 KB	Output is correct
11	Correct	273 ms	6524 KB	Output is correct
12	Correct	279 ms	6524 KB	Output is correct
13	Correct	246 ms	6524 KB	Output is correct
14	Correct	297 ms	6524 KB	Output is correct
15	Correct	254 ms	6872 KB	Output is correct
16	Correct	262 ms	6872 KB	Output is correct
17	Correct	266 ms	6872 KB	Output is correct
18	Correct	191 ms	8576 KB	Output is correct
19	Correct	224 ms	8576 KB	Output is correct
20	Correct	265 ms	8576 KB	Output is correct
21	Correct	313 ms	8576 KB	Output is correct
22	Correct	336 ms	8576 KB	Output is correct
23	Correct	416 ms	8576 KB	Output is correct
24	Correct	392 ms	8576 KB	Output is correct
25	Correct	398 ms	8824 KB	Output is correct
26	Correct	382 ms	8824 KB	Output is correct
27	Correct	427 ms	8824 KB	Output is correct
28	Correct	245 ms	9692 KB	Output is correct
29	Correct	273 ms	9692 KB	Output is correct
30	Correct	317 ms	9692 KB	Output is correct
31	Correct	346 ms	9692 KB	Output is correct
32	Correct	454 ms	9692 KB	Output is correct
33	Correct	265 ms	9692 KB	Output is correct
34	Correct	321 ms	9692 KB	Output is correct
35	Correct	372 ms	21816 KB	Output is correct
36	Correct	225 ms	34012 KB	Output is correct
37	Correct	277 ms	49800 KB	Output is correct
38	Correct	273 ms	61628 KB	Output is correct
39	Runtime error	360 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.
40	Halted	0 ms	0 KB	-

답안 #64572

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 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
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0