Submission #476492

#	Time	Username	Problem	Language	Result	Execution time	Memory
476492		keta_tsimakuridze	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	695 ms	65540 KiB

snake_escaping

#include<bits/stdc++.h>
#define f first
#define s second
////#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1048576 + 5, mod = 1e9 + 7; // !
int t,dp1[N][22],dp2[N][22],L,q;
vector<int> cnt[4];
main(){
			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
            cin >> L >> q;
            string s;
            cin >> s;
            for(int i = 0; i < (1 << L); i++) { 
                        dp1[i][0] = s[i] - '0';
                        for(int j = 0; j < L; j++) {
                                    if(j) dp1[i][j] = dp1[i][j - 1];
                                    if((1 << j) & i) dp1[i][j] += dp1[i ^ (1 << j)][j];
                        }
            }
            for(int i = (1 << L) - 1; i >= 0; i--) {
                        dp2[i][0] = s[i] - '0';
                        for(int j = 0; j < L; j++) {
                                    if(j) dp2[i][j] = dp2[i][j - 1];
                                    if(!((1 << j) & i)) dp2[i][j] += dp2[i ^ (1 << j)][j];
                        }
            }
            while(q--) {
                        string t;
                        cin >> t;
                        int x = 0;
                        reverse(t.begin(),t.end());
                        int c = 0, a = 0, b = 0;
                        for(int i = 0; i < 3; i++) cnt[i].clear();
                        for(int i = 0; i < t.size(); i++) {
                                    if(t[i] == '0') cnt[0].push_back(i), a += 1 << i;
                                    else if(t[i] == '1') cnt[1].push_back(i),b += 1 << i;
                                    else cnt[2].push_back(i),c += 1 << i;
                        }
                        long long ans = 0;
                        if(cnt[2].size() < 7) {
                        		
                                    for(int i = c;; i = (i - 1) & c) {
                                                ans += s[i | b] - '0';
                                                if(!i) break;
                                    }
                        }
                        else if(cnt[1].size() < 7) {	
                                    int p = __builtin_popcount(b) % 2;
                                    for(int i = b;; i = (i - 1) & b) {
                                            ans += (__builtin_popcount(i) % 2 == p ? 1 : -1)
                                                    * dp1[i | c][L - 1];
                                            if(!i) break;
                                                    
                                    }
                        }
                        else {
                                    for(int i = a;; i = (i - 1) & a) {
                                            ans += (__builtin_popcount(i) % 2 == 0 ? 1 : -1)
                                                       * dp2[i | b][L - 1];
                                            if(!i) break;    
                                    }
                        }
                        cout << ans << "\n";
            }
 }

Compilation message (stderr)

snake_escaping.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:36:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                         for(int i = 0; i < t.size(); i++) {
      |                                        ~~^~~~~~~~~~
snake_escaping.cpp:32:29: warning: unused variable 'x' [-Wunused-variable]
   32 |                         int x = 0;
      |                             ^

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