oj.uz

Submission #675727

# Submission time Handle Problem Language Result Execution time Memory
675727 2022-12-27T19:05:51 Z MilosMilutinovic Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 20044 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 << 22);
int n, q;
char s[N];
char t[N];
int sub[N];
int super[N];

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

	scanf("%d%d", &n, &q);
	scanf("%s", s);
	for (int mask = 0; mask < (1 << n); mask++)
		for (int submask = 0; submask < (1 << n); submask++)
			if ((mask & submask) == submask)
				sub[mask] += (int)(s[submask] - '0');
	for (int mask = 0; mask < (1 << n); mask++)
		for (int supermask = 0; supermask < (1 << n); supermask++)
			if ((mask & supermask) == mask)
				super[mask] += (int)(s[supermask] - '0');
	while(q--) {
		scanf("%s", t);
		reverse(t, t + n);
		vector<int> zero, one, qmark;
		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);
		}
		int 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 += super[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] == '1' || 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 << zero[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:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~
snake_escaping.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%s", t);
      |   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 856 ms 15004 KB Output is correct
12 Correct 752 ms 14640 KB Output is correct
13 Correct 649 ms 13960 KB Output is correct
14 Correct 646 ms 14088 KB Output is correct
15 Correct 1154 ms 15184 KB Output is correct
16 Correct 806 ms 14240 KB Output is correct
17 Correct 753 ms 14160 KB Output is correct
18 Correct 380 ms 16112 KB Output is correct
19 Correct 537 ms 13048 KB Output is correct
20 Correct 811 ms 14664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 856 ms 15004 KB Output is correct
12 Correct 752 ms 14640 KB Output is correct
13 Correct 649 ms 13960 KB Output is correct
14 Correct 646 ms 14088 KB Output is correct
15 Correct 1154 ms 15184 KB Output is correct
16 Correct 806 ms 14240 KB Output is correct
17 Correct 753 ms 14160 KB Output is correct
18 Correct 380 ms 16112 KB Output is correct
19 Correct 537 ms 13048 KB Output is correct
20 Correct 811 ms 14664 KB Output is correct
21 Correct 702 ms 18060 KB Output is correct
22 Correct 1099 ms 18208 KB Output is correct
23 Correct 939 ms 17236 KB Output is correct
24 Correct 892 ms 17060 KB Output is correct
25 Correct 765 ms 19076 KB Output is correct
26 Correct 1050 ms 17728 KB Output is correct
27 Correct 1060 ms 17708 KB Output is correct
28 Correct 510 ms 20044 KB Output is correct
29 Correct 668 ms 15996 KB Output is correct
30 Correct 951 ms 18284 KB Output is correct
31 Correct 1458 ms 18184 KB Output is correct
32 Correct 1050 ms 18156 KB Output is correct
33 Correct 790 ms 17048 KB Output is correct
34 Correct 951 ms 16972 KB Output is correct
35 Correct 1062 ms 17472 KB Output is correct
36 Correct 450 ms 16024 KB Output is correct
37 Correct 1302 ms 18000 KB Output is correct
38 Correct 694 ms 16052 KB Output is correct
39 Correct 968 ms 17192 KB Output is correct
40 Correct 906 ms 17224 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Execution timed out 2073 ms 2724 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 856 ms 15004 KB Output is correct
12 Correct 752 ms 14640 KB Output is correct
13 Correct 649 ms 13960 KB Output is correct
14 Correct 646 ms 14088 KB Output is correct
15 Correct 1154 ms 15184 KB Output is correct
16 Correct 806 ms 14240 KB Output is correct
17 Correct 753 ms 14160 KB Output is correct
18 Correct 380 ms 16112 KB Output is correct
19 Correct 537 ms 13048 KB Output is correct
20 Correct 811 ms 14664 KB Output is correct
21 Correct 702 ms 18060 KB Output is correct
22 Correct 1099 ms 18208 KB Output is correct
23 Correct 939 ms 17236 KB Output is correct
24 Correct 892 ms 17060 KB Output is correct
25 Correct 765 ms 19076 KB Output is correct
26 Correct 1050 ms 17728 KB Output is correct
27 Correct 1060 ms 17708 KB Output is correct
28 Correct 510 ms 20044 KB Output is correct
29 Correct 668 ms 15996 KB Output is correct
30 Correct 951 ms 18284 KB Output is correct
31 Correct 1458 ms 18184 KB Output is correct
32 Correct 1050 ms 18156 KB Output is correct
33 Correct 790 ms 17048 KB Output is correct
34 Correct 951 ms 16972 KB Output is correct
35 Correct 1062 ms 17472 KB Output is correct
36 Correct 450 ms 16024 KB Output is correct
37 Correct 1302 ms 18000 KB Output is correct
38 Correct 694 ms 16052 KB Output is correct
39 Correct 968 ms 17192 KB Output is correct
40 Correct 906 ms 17224 KB Output is correct
41 Execution timed out 2073 ms 2724 KB Time limit exceeded
42 Halted 0 ms 0 KB -