제출 #699502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699502		badont	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	634 ms	28400 KiB

snake_escaping

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25