oj.uz

Submission #699502

# Submission time Handle Problem Language Result Execution time Memory
699502 2023-02-17T07:57:17 Z badont Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 634 ms 28400 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;

void solve() {
	ll n, q;
	string a;

	cin >> n >> q >> a;

	debug(n, q, a);

	vector<ll> sub(1 << n), super(1 << n);

	ll big = (1LL << n) - 1;
	F0R (i, 1 << n) {
		sub[i] = a[i] - '0';
		super[i ^ big] = a[i] - '0';
	}

	F0R (i, n) F0R (msk, 1 << n) if ((msk >> i) & 1) {
		sub[msk] += sub[msk ^ (1 << i)];
		super[msk] += super[msk ^ (1 << i)];
	}

	vector new_super = super;
	F0R (msk, 1 << n) {
		new_super[big ^ msk] = super[msk];
	}
	swap(new_super, super);
	new_super.clear();

	//debug(super);
	//debug(super[1]);;

	//debug(super);
	//debug(sub);

	while (q--) {
		string t; cin >> t;
		reverse(all(t));

		int zc = 0, oc = 0, qc = 0;
		for (auto u : t) {
			if (u == '0') {
				zc++;
			} else if (u == '1') {
				oc++;
			} else {
				qc++;
			}
		}

		ll qmsk = 0, omsk = 0, zmsk = 0;
		F0R (i, n) if (t[i] == '?') {
			qmsk |= 1LL << i;
		}

		F0R (i, n) if (t[i] == '1') {
			omsk |= 1LL << i;
		}

		F0R (i, n) if (t[i] == '0') {
			zmsk |= 1LL << i;
		}

		if (oc <= 6) {
			//zeros fixed (sub)
			ll ans = 0;
			for (int i = omsk; i >= 0; i = (i - 1) & omsk) {
				ll pie = (__builtin_popcount(i) % 2 == __builtin_popcount(omsk) % 2 ? 1 : -1);
				ans += pie * sub[(i | qmsk)];
				if (i == 0) break;
			} 
			cout << ans << '\n';
		} else if (zc <= 6) {
			//ones fixed (super)
			ll ans = 0;
 			for (int i = zmsk; i >= 0; i = (i - 1) & zmsk) {
 				ll pie = (__builtin_popcount(i) % 2 == 0 ? 1 : -1);
 				ans += pie * super[i | omsk];
 				//debug(ans, i | omsk);
 				if (i == 0) break;
			}
			cout << ans << '\n';
		} else if (qc <= 6) {
			ll ans = 0;
			for (int i = qmsk; i >= 0; i = (i - 1) & qmsk) {
				ans += a[qmsk | omsk] - '0';
				if (i == 0) break;
			}
			cout << ans << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
snake_escaping.cpp:47:2: note: in expansion of macro 'debug'
   47 |  debug(n, q, a);
      |  ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 328 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 372 ms 12068 KB Output is correct
12 Correct 290 ms 11804 KB Output is correct
13 Correct 367 ms 11064 KB Output is correct
14 Correct 357 ms 11180 KB Output is correct
15 Correct 317 ms 12084 KB Output is correct
16 Correct 420 ms 11276 KB Output is correct
17 Correct 419 ms 11208 KB Output is correct
18 Correct 193 ms 13136 KB Output is correct
19 Correct 359 ms 10188 KB Output is correct
20 Correct 401 ms 11720 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 372 ms 12068 KB Output is correct
12 Correct 290 ms 11804 KB Output is correct
13 Correct 367 ms 11064 KB Output is correct
14 Correct 357 ms 11180 KB Output is correct
15 Correct 317 ms 12084 KB Output is correct
16 Correct 420 ms 11276 KB Output is correct
17 Correct 419 ms 11208 KB Output is correct
18 Correct 193 ms 13136 KB Output is correct
19 Correct 359 ms 10188 KB Output is correct
20 Correct 401 ms 11720 KB Output is correct
21 Correct 574 ms 12208 KB Output is correct
22 Correct 354 ms 12304 KB Output is correct
23 Correct 474 ms 11468 KB Output is correct
24 Correct 476 ms 11364 KB Output is correct
25 Correct 390 ms 13308 KB Output is correct
26 Correct 513 ms 11744 KB Output is correct
27 Correct 503 ms 11624 KB Output is correct
28 Correct 207 ms 14292 KB Output is correct
29 Correct 539 ms 10272 KB Output is correct
30 Correct 459 ms 12412 KB Output is correct
31 Correct 472 ms 12132 KB Output is correct
32 Correct 468 ms 12316 KB Output is correct
33 Correct 392 ms 11024 KB Output is correct
34 Correct 508 ms 11188 KB Output is correct
35 Correct 521 ms 11720 KB Output is correct
36 Correct 229 ms 10228 KB Output is correct
37 Correct 337 ms 12140 KB Output is correct
38 Correct 526 ms 10204 KB Output is correct
39 Correct 634 ms 11348 KB Output is correct
40 Correct 528 ms 11116 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 73 ms 28324 KB Output is correct
12 Correct 76 ms 28400 KB Output is correct
13 Incorrect 86 ms 28312 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 372 ms 12068 KB Output is correct
12 Correct 290 ms 11804 KB Output is correct
13 Correct 367 ms 11064 KB Output is correct
14 Correct 357 ms 11180 KB Output is correct
15 Correct 317 ms 12084 KB Output is correct
16 Correct 420 ms 11276 KB Output is correct
17 Correct 419 ms 11208 KB Output is correct
18 Correct 193 ms 13136 KB Output is correct
19 Correct 359 ms 10188 KB Output is correct
20 Correct 401 ms 11720 KB Output is correct
21 Correct 574 ms 12208 KB Output is correct
22 Correct 354 ms 12304 KB Output is correct
23 Correct 474 ms 11468 KB Output is correct
24 Correct 476 ms 11364 KB Output is correct
25 Correct 390 ms 13308 KB Output is correct
26 Correct 513 ms 11744 KB Output is correct
27 Correct 503 ms 11624 KB Output is correct
28 Correct 207 ms 14292 KB Output is correct
29 Correct 539 ms 10272 KB Output is correct
30 Correct 459 ms 12412 KB Output is correct
31 Correct 472 ms 12132 KB Output is correct
32 Correct 468 ms 12316 KB Output is correct
33 Correct 392 ms 11024 KB Output is correct
34 Correct 508 ms 11188 KB Output is correct
35 Correct 521 ms 11720 KB Output is correct
36 Correct 229 ms 10228 KB Output is correct
37 Correct 337 ms 12140 KB Output is correct
38 Correct 526 ms 10204 KB Output is correct
39 Correct 634 ms 11348 KB Output is correct
40 Correct 528 ms 11116 KB Output is correct
41 Correct 73 ms 28324 KB Output is correct
42 Correct 76 ms 28400 KB Output is correct
43 Incorrect 86 ms 28312 KB Output isn't correct
44 Halted 0 ms 0 KB -