Submission #154127

#	Time	Username	Problem	Language	Result	Execution time	Memory
154127		ryansee	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	976 ms	43416 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcount((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (20)
int L, Q;
string S;
int sum0[1<<MAXN], sum1[1<<MAXN], num[1<<MAXN];
string gug(ll x, ll place) {
	-- place;
	assert(x <= (1<<(place+1))-1);
	string res="";
	for(ll i=place; i>=0; --i) if((1<<i)&x) res+='1'; else res+='0';
	return res;
}
int main()
{
	FAST
	cin>>L>>Q;
	cin>>S;
	FOR(i,0,(1<<L)-1) {
		sum0[(~i)&((1<<L)-1)] += S[i]-'0';
		sum1[i] += S[i]-'0'; 
		num[i]=btinpct(i);
	}
	FOR(j,0,L-1) {
		FOR(i,0,(1<<L)-1) {
			if( ((1<<j)&i) == 0 ) sum0[i] += sum0[i^(1<<j)], sum1[i] += sum1[i^(1<<j)];
		}
	}
	FOR(ii,0,Q-1) {
		string Q; cin>>Q;
		reverse(all(Q)); assert(Q.size()==L);
		int a=0, b=0, c=0, na=0, nb=0, nc=0;
		FOR(i,0,L-1) {
			if(Q[i] == '0') a += 1<<i, ++na;
			if(Q[i] == '1') b += 1<<i, ++nb;
			if(Q[i] == '?') c += 1<<i, ++nc;
		}
		int ans=0;
		if((na <= nb && na <= nc)) { // a
			ans += sum1[b]; // a will not clash bit with b, cos in Q[pos] only can be 1 character lol
			for(int j=a; j>0; j=(j-1)&a) { assert((j&b)==0);
				if(num[j] & 1) ans -= sum1[j|b];
				else ans += sum1[j|b];
			}
		} else if(nb <= na && nb <= nc) { // b
			ans += sum0[a];
			for(int j=b; j>0; j=(j-1)&b) {
				if(num[j] & 1) ans -= sum0[j|a];
				else ans += sum0[j|a];
			}
		} else { // c
			for(int i=c; i>0; i=(i-1)&c) ans += S[i|b]-'0';// (i&b) == 0
			ans += S[b]-'0';
		}
		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from snake_escaping.cpp:1:
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:59:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   reverse(all(Q)); assert(Q.size()==L);
                           ~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25