Submission #49493

#	Time	Username	Problem	Language	Result	Execution time	Memory
49493		RezwanArefin01	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2072 ms	65536 KiB

snake_escaping

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize ("unroll-loops")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
     
    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
    typedef pair<int, int> ii; 
     
    int dp[1 << 20], dp2[1 << 20]; ll ans; 
    char b[1 << 20], s[1 << 20];
    int l, q;
     
    void recurr1(int i, int num, int tot) {
    	if(i == l) {
    		if(tot & 1) ans -= dp[num];
    		else ans += dp[num];
    		return; 
    	}
    	if(s[i] == '0') recurr1(i + 1, num << 1, tot); 
    	else if(s[i] == '?') recurr1(i + 1, num << 1 | 1, tot);
    	else {
    		recurr1(i + 1, num << 1 | 1, tot); 
    		recurr1(i + 1, num << 1, tot + 1);
    	}
    }
     
    void recurr0(int i, int num, int tot) {
    	if(i == l) {
    		if(tot & 1) ans -= dp2[num];
    		else ans += dp2[num];
    		return; 
    	}
    	if(s[i] == '1') recurr0(i + 1, num << 1 | 1, tot);
    	else if(s[i] == '?') recurr0(i + 1, num << 1, tot);
    	else {
    		recurr0(i + 1, num << 1, tot);
    		recurr0(i + 1, num << 1 | 1, tot + 1);
    	}
    }
     
    void recurrw0t(int i, int num) {
    	if(i == l) {
    		ans += b[num] - '0';
    		return;
    	} 
    	if(s[i] == '?') {
    		recurrw0t(i + 1, num << 1 | 1);
    		recurrw0t(i + 1, num << 1);
    	} else recurrw0t(i + 1, (num << 1) + (s[i] == '1'));
    }
    int main(int argc, char const *argv[]) {
    #ifdef LOCAL_TESTING
    	freopen("in", "r", stdin);
    #endif
    	scanf("%d %d", &l, &q);
    	scanf(" %s", b);
     
    	for(int i = 0; i < (1 << l); ++i) 
    		dp[i] = dp2[i] = b[i] - '0';
    	
    	for(int i = 0; i < l; ++i) 
    		for(int j = 0; j < (1 << l); ++j) 
    			if(j >> i & 1) dp[j] += dp[j ^ (1 << i)];
     
    	for(int i = 0; i < l; ++i) 
    		for(int j = 0; j < (1 << l); ++j) 
    			if(~j >> i & 1) dp2[j] += dp2[j | (1 << i)];
     
    	while(q--) {
    		scanf(" %s", s);
    		int n0 = 0, n1 = 0, nw0t = 0; 
    		for(int i = 0; i < l; ++i) {
    			n0 += s[i] == '0';
    			n1 += s[i] == '1';
    			nw0t += s[i] == '?';
    		}
     
    		if(!n1) {
    			int num = 0;
    			for(int i = 0; i < l; ++i) 
    				num = (num << 1) + (s[i] == '?');
    			printf("%lld\n", dp[num]);
    		} else if(nw0t == 0) {
    			int num = 0;
    			for(int i = 0; i < l; ++i) 
    				num = (num << 1) + (s[i] == '1');
    			printf("%c\n", b[num]);
    		} else {
    			ans = 0;
    			if(nw0t <= n1 && nw0t <= n0) recurrw0t(0, 0);
    			else if(n1 <= nw0t && n1 <= n0) recurr1(0, 0, 0);
    			else recurr0(0, 0, 0);
    			printf("%lld\n", ans);
    		}
    	}
    }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main(int, const char**)':
snake_escaping.cpp:84:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
        printf("%lld\n", dp[num]);
                         ~~~~~~~^
snake_escaping.cpp:57:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d", &l, &q);
      ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:58:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf(" %s", b);
      ~~~~~^~~~~~~~~~
snake_escaping.cpp:72:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %s", s);
       ~~~~~^~~~~~~~~~

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