oj.uz

Submission #675746

# Submission time Handle Problem Language Result Execution time Memory
675746 2022-12-27T19:37:05 Z MilosMilutinovic Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 1578 ms 23200 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = (1 << 20);
int n, q;
char s[N];
char t[22];
int sub[N];
int sup[N];
vector<int> zero;
vector<int> one;
vector<int> qmark;

char nextChar() {
	char c = getchar();
	while (!isdigit(c) && c != '?') c = getchar();
	return c;
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &q);
	for (int i = 0; i < (1 << n); i++)
		s[i] = nextChar();
	for (int i = 0; i < (1 << n); i++) {
		sub[i] = (int)(s[i] - '0');
		sup[i] = (int)(s[i] - '0');
	}
	for (int i = 0; i < n; i++)
		for (int mask = 0; mask < (1 << n); mask++)
			if (mask >> i & 1)
				sub[mask] += sub[mask ^ (1 << i)];
	for (int i = 0; i < n; i++)
		for (int mask = (1 << n) - 1; mask >= 0; mask--)
			if (!(mask >> i & 1))
				sup[mask] += sup[mask ^ (1 << i)];
	int tmask;
	while(q--) {
		for (int i = 0; i < n; i++)
			t[i] = nextChar();
		reverse(t, t + n);
		zero.clear();
		one.clear();
		qmark.clear();
		for (int i = 0; i < n; i++) {
			if (t[i] == '0') zero.push_back(i);
			if (t[i] == '1') one.push_back(i);
			if (t[i] == '?') qmark.push_back(i);
		}
		tmask = 0;
		for (int i = 0; i < n; i++)
			if (t[i] == '1')
				tmask += (1 << i);
		int ans = 0;
		if (qmark.size() <= 6) {
			int sz = qmark.size();
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << qmark[i]);
				ans += (int)(s[nmask] - '0');
			}
		} else if (zero.size() <= 6) {
			int sz = zero.size();
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << zero[i]);
				ans += sup[nmask] * (__builtin_popcount(mask) % 2 == 0 ? 1 : -1);
			}
		} else {
			assert(one.size() <= 6);
			int sz = one.size();
			tmask = 0;
			for (int i = 0; i < n; i++)
				if (t[i] == '?')
					tmask += (1 << i);
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << one[i]);
				ans += sub[nmask] * ((sz - __builtin_popcount(mask)) % 2 == 0 ? 1 : -1);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 477 ms 4400 KB Output is correct
12 Correct 483 ms 3980 KB Output is correct
13 Correct 347 ms 3304 KB Output is correct
14 Correct 311 ms 3356 KB Output is correct
15 Correct 792 ms 4388 KB Output is correct
16 Correct 444 ms 3540 KB Output is correct
17 Correct 430 ms 3428 KB Output is correct
18 Correct 188 ms 5336 KB Output is correct
19 Correct 243 ms 2292 KB Output is correct
20 Correct 482 ms 4052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 477 ms 4400 KB Output is correct
12 Correct 483 ms 3980 KB Output is correct
13 Correct 347 ms 3304 KB Output is correct
14 Correct 311 ms 3356 KB Output is correct
15 Correct 792 ms 4388 KB Output is correct
16 Correct 444 ms 3540 KB Output is correct
17 Correct 430 ms 3428 KB Output is correct
18 Correct 188 ms 5336 KB Output is correct
19 Correct 243 ms 2292 KB Output is correct
20 Correct 482 ms 4052 KB Output is correct
21 Correct 357 ms 4416 KB Output is correct
22 Correct 743 ms 4520 KB Output is correct
23 Correct 503 ms 3624 KB Output is correct
24 Correct 460 ms 3488 KB Output is correct
25 Correct 414 ms 5436 KB Output is correct
26 Correct 612 ms 3872 KB Output is correct
27 Correct 551 ms 3824 KB Output is correct
28 Correct 262 ms 6464 KB Output is correct
29 Correct 306 ms 2448 KB Output is correct
30 Correct 529 ms 4504 KB Output is correct
31 Correct 876 ms 4464 KB Output is correct
32 Correct 560 ms 4456 KB Output is correct
33 Correct 378 ms 3392 KB Output is correct
34 Correct 476 ms 3400 KB Output is correct
35 Correct 576 ms 3900 KB Output is correct
36 Correct 224 ms 2380 KB Output is correct
37 Correct 788 ms 4380 KB Output is correct
38 Correct 332 ms 2336 KB Output is correct
39 Correct 487 ms 3608 KB Output is correct
40 Correct 496 ms 3476 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 74 ms 9804 KB Output is correct
12 Correct 80 ms 9804 KB Output is correct
13 Correct 92 ms 9640 KB Output is correct
14 Correct 115 ms 9772 KB Output is correct
15 Correct 90 ms 9772 KB Output is correct
16 Correct 119 ms 9644 KB Output is correct
17 Correct 109 ms 9676 KB Output is correct
18 Correct 64 ms 9912 KB Output is correct
19 Correct 69 ms 9612 KB Output is correct
20 Correct 77 ms 9804 KB Output is correct
21 Correct 97 ms 9652 KB Output is correct
22 Correct 123 ms 9656 KB Output is correct
23 Correct 77 ms 9548 KB Output is correct
24 Correct 101 ms 9684 KB Output is correct
25 Correct 101 ms 9644 KB Output is correct
26 Correct 81 ms 9516 KB Output is correct
27 Correct 76 ms 9752 KB Output is correct
28 Correct 70 ms 9524 KB Output is correct
29 Correct 87 ms 9672 KB Output is correct
30 Correct 99 ms 9616 KB Output is correct
31 Correct 77 ms 9648 KB Output is correct
32 Correct 117 ms 9680 KB Output is correct
33 Correct 101 ms 9660 KB Output is correct
34 Correct 61 ms 9516 KB Output is correct
35 Correct 95 ms 9660 KB Output is correct
36 Correct 103 ms 9824 KB Output is correct
37 Correct 100 ms 9616 KB Output is correct
38 Correct 101 ms 9696 KB Output is correct
39 Correct 110 ms 9660 KB Output is correct
40 Correct 94 ms 9676 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 477 ms 4400 KB Output is correct
12 Correct 483 ms 3980 KB Output is correct
13 Correct 347 ms 3304 KB Output is correct
14 Correct 311 ms 3356 KB Output is correct
15 Correct 792 ms 4388 KB Output is correct
16 Correct 444 ms 3540 KB Output is correct
17 Correct 430 ms 3428 KB Output is correct
18 Correct 188 ms 5336 KB Output is correct
19 Correct 243 ms 2292 KB Output is correct
20 Correct 482 ms 4052 KB Output is correct
21 Correct 357 ms 4416 KB Output is correct
22 Correct 743 ms 4520 KB Output is correct
23 Correct 503 ms 3624 KB Output is correct
24 Correct 460 ms 3488 KB Output is correct
25 Correct 414 ms 5436 KB Output is correct
26 Correct 612 ms 3872 KB Output is correct
27 Correct 551 ms 3824 KB Output is correct
28 Correct 262 ms 6464 KB Output is correct
29 Correct 306 ms 2448 KB Output is correct
30 Correct 529 ms 4504 KB Output is correct
31 Correct 876 ms 4464 KB Output is correct
32 Correct 560 ms 4456 KB Output is correct
33 Correct 378 ms 3392 KB Output is correct
34 Correct 476 ms 3400 KB Output is correct
35 Correct 576 ms 3900 KB Output is correct
36 Correct 224 ms 2380 KB Output is correct
37 Correct 788 ms 4380 KB Output is correct
38 Correct 332 ms 2336 KB Output is correct
39 Correct 487 ms 3608 KB Output is correct
40 Correct 496 ms 3476 KB Output is correct
41 Correct 74 ms 9804 KB Output is correct
42 Correct 80 ms 9804 KB Output is correct
43 Correct 92 ms 9640 KB Output is correct
44 Correct 115 ms 9772 KB Output is correct
45 Correct 90 ms 9772 KB Output is correct
46 Correct 119 ms 9644 KB Output is correct
47 Correct 109 ms 9676 KB Output is correct
48 Correct 64 ms 9912 KB Output is correct
49 Correct 69 ms 9612 KB Output is correct
50 Correct 77 ms 9804 KB Output is correct
51 Correct 97 ms 9652 KB Output is correct
52 Correct 123 ms 9656 KB Output is correct
53 Correct 77 ms 9548 KB Output is correct
54 Correct 101 ms 9684 KB Output is correct
55 Correct 101 ms 9644 KB Output is correct
56 Correct 81 ms 9516 KB Output is correct
57 Correct 76 ms 9752 KB Output is correct
58 Correct 70 ms 9524 KB Output is correct
59 Correct 87 ms 9672 KB Output is correct
60 Correct 99 ms 9616 KB Output is correct
61 Correct 77 ms 9648 KB Output is correct
62 Correct 117 ms 9680 KB Output is correct
63 Correct 101 ms 9660 KB Output is correct
64 Correct 61 ms 9516 KB Output is correct
65 Correct 95 ms 9660 KB Output is correct
66 Correct 103 ms 9824 KB Output is correct
67 Correct 100 ms 9616 KB Output is correct
68 Correct 101 ms 9696 KB Output is correct
69 Correct 110 ms 9660 KB Output is correct
70 Correct 94 ms 9676 KB Output is correct
71 Correct 613 ms 14452 KB Output is correct
72 Correct 740 ms 14752 KB Output is correct
73 Correct 808 ms 13152 KB Output is correct
74 Correct 1578 ms 13420 KB Output is correct
75 Correct 728 ms 21224 KB Output is correct
76 Correct 1417 ms 19400 KB Output is correct
77 Correct 1268 ms 19404 KB Output is correct
78 Correct 386 ms 23200 KB Output is correct
79 Correct 551 ms 17152 KB Output is correct
80 Correct 658 ms 20216 KB Output is correct
81 Correct 1006 ms 20256 KB Output is correct
82 Correct 1506 ms 19264 KB Output is correct
83 Correct 625 ms 18348 KB Output is correct
84 Correct 1076 ms 19216 KB Output is correct
85 Correct 1201 ms 19496 KB Output is correct
86 Correct 335 ms 17324 KB Output is correct
87 Correct 611 ms 20404 KB Output is correct
88 Correct 509 ms 17372 KB Output is correct
89 Correct 799 ms 19204 KB Output is correct
90 Correct 1077 ms 19352 KB Output is correct
91 Correct 623 ms 18144 KB Output is correct
92 Correct 1455 ms 18968 KB Output is correct
93 Correct 1165 ms 18772 KB Output is correct
94 Correct 341 ms 15584 KB Output is correct
95 Correct 1048 ms 17240 KB Output is correct
96 Correct 1052 ms 16556 KB Output is correct
97 Correct 1000 ms 15924 KB Output is correct
98 Correct 1014 ms 15168 KB Output is correct
99 Correct 1042 ms 14364 KB Output is correct
100 Correct 984 ms 13620 KB Output is correct