Submission #1146761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146761		tnt	Snake Escaping (JOI18_snake_escaping)	C++20	Compilation error	0 ms	0 KiB

snake_escaping

using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long
//#define sort(all(v)) sort(v.begin(),v.end())

int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e9;



signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    int l,q;
    cin >> l >> q;                                
    string s;                                      
    cin >> s;
    vector <ll> dp((1 << l)),dp1((1 << l));
    for(int i = 0; i < (1 << l); i++){
     dp[i] = dp1[i] = s[i] - '0';
    }
    for(int i = 0; i < l; i++){
     for(int mask = (1 << l) - 1; mask >= 0;mask--){
      if(!(mask >> i & 1)){
       dp1[mask] += dp1[(mask ^ (1 << i))];
      }
     }
    }
    for(int i = 0; i < l; i++){
     for(int mask = 0; mask < (1 << l) ;mask++){
      if((mask >> i & 1)){
       dp[mask] += dp[(mask ^ (1 << i))];
      }
     }
    }                 
    while(q--){
        string t;                                 
        cin >> t;
        int cnt = 0,cnt1 = 0;
        for(int i = 0; i < l; i++){
         if(t[i] == '?') cnt++;
         else if(t[i] == '1') cnt1++;
        }
        if(cnt <= 6){
            int sum = 0,p = 0;
            ll ans = 0;
         vector <int> v;
         for(int i = t.size() - 1; i >= 0;i--){
          if(t[i] == '1'){
           sum += (1 << p);
          }
          else if(t[i] == '?'){
           v.pb(p);
          }
          p++;
         }
         for(int mask = 0; mask < (1 << cnt); mask++){
          int sum1 = 0;
          for(int j = 0;j < cnt; j++){
           if((mask >> j & 1) == 1){
            sum1 += (1 << v[j]);
           }
          }
          ans += s[sum + sum1] - '0';
         }
         cout << ans << '\n';
        }               
        else if(cnt1 > 6){
         int p = 0,sum = 0;
         ll ans = 0;
         for(int i =  t.size() - 1; i >= 0; i--){
          if(t[i] == '1') sum += (1 << p);
          p++;
         }
         ans = dp1[sum];
         vector <int> v;
         p = 0;
         for(int i =  t.size() - 1; i >= 0; i--){
          if(t[i] == '0') v.pb(p);
          p++;
         }
         for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
          int sum1 = sum;
          for(int j = 0; j < v.size(); j++){
           if((mask2 >> j & 1) == 1)sum1 += (1 << v[j]);
          }
          if(__builtin_popcount(mask2) & 1){
           ans -= dp1[sum1];
          }
          else ans += dp1[sum1];
         }
         cout << ans << '\n';
        }  
        else{
         int p = 0,sum = 0;
         ll ans = 0;
         for(int i =  t.size() - 1; i >= 0; i--){
          if(t[i] != '0') sum += (1 << p);
          p++;
         }
         ans = dp[sum];
         vector <int> v;
         p = 0;
         for(int i =  t.size() - 1; i >= 0; i--){
          if(t[i] == '1') v.pb(p);
          p++;
         }
         for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
          int sum1 = sum;
          for(int j = 0; j < v.size(); j++){
           if((mask2 >> j & 1) == 1)sum1 -= (1 << v[j]);
          }
          if(__builtin_popcount(mask2) & 1){
           ans -= dp[sum1];
          }
          else ans += dp[sum1];
         }
         cout << ans << '\n';

        }

    }
    
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:19:5: error: 'cin' was not declared in this scope
   19 |     cin >> l >> q;
      |     ^~~
snake_escaping.cpp:1:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
  +++ |+#include <iostream>
    1 | using namespace std;
snake_escaping.cpp:20:5: error: 'string' was not declared in this scope
   20 |     string s;
      |     ^~~~~~
snake_escaping.cpp:1:1: note: 'std::string' is defined in header '<string>'; did you forget to '#include <string>'?
  +++ |+#include <string>
    1 | using namespace std;
snake_escaping.cpp:21:12: error: 's' was not declared in this scope
   21 |     cin >> s;
      |            ^
snake_escaping.cpp:22:5: error: 'vector' was not declared in this scope
   22 |     vector <ll> dp((1 << l)),dp1((1 << l));
      |     ^~~~~~
snake_escaping.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using namespace std;
snake_escaping.cpp:6:12: error: expected primary-expression before 'long'
    6 | #define ll long long
      |            ^~~~
snake_escaping.cpp:22:13: note: in expansion of macro 'll'
   22 |     vector <ll> dp((1 << l)),dp1((1 << l));
      |             ^~
snake_escaping.cpp:24:6: error: 'dp' was not declared in this scope
   24 |      dp[i] = dp1[i] = s[i] - '0';
      |      ^~
snake_escaping.cpp:24:14: error: 'dp1' was not declared in this scope
   24 |      dp[i] = dp1[i] = s[i] - '0';
      |              ^~~
snake_escaping.cpp:29:8: error: 'dp1' was not declared in this scope
   29 |        dp1[mask] += dp1[(mask ^ (1 << i))];
      |        ^~~
snake_escaping.cpp:36:8: error: 'dp' was not declared in this scope
   36 |        dp[mask] += dp[(mask ^ (1 << i))];
      |        ^~
snake_escaping.cpp:41:15: error: expected ';' before 't'
   41 |         string t;
      |               ^~
      |               ;
snake_escaping.cpp:42:16: error: 't' was not declared in this scope
   42 |         cin >> t;
      |                ^
snake_escaping.cpp:51:18: error: expected primary-expression before 'int'
   51 |          vector <int> v;
      |                  ^~~
snake_escaping.cpp:57:12: error: 'v' was not declared in this scope
   57 |            v.pb(p);
      |            ^
snake_escaping.cpp:65:27: error: 'v' was not declared in this scope
   65 |             sum1 += (1 << v[j]);
      |                           ^
snake_escaping.cpp:70:10: error: 'cout' was not declared in this scope
   70 |          cout << ans << '\n';
      |          ^~~~
snake_escaping.cpp:70:10: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
snake_escaping.cpp:79:16: error: 'dp1' was not declared in this scope
   79 |          ans = dp1[sum];
      |                ^~~
snake_escaping.cpp:80:18: error: expected primary-expression before 'int'
   80 |          vector <int> v;
      |                  ^~~
snake_escaping.cpp:83:27: error: 'v' was not declared in this scope
   83 |           if(t[i] == '0') v.pb(p);
      |                           ^
snake_escaping.cpp:86:43: error: 'v' was not declared in this scope
   86 |          for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
      |                                           ^
snake_escaping.cpp:96:10: error: 'cout' was not declared in this scope
   96 |          cout << ans << '\n';
      |          ^~~~
snake_escaping.cpp:96:10: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
snake_escaping.cpp:105:16: error: 'dp' was not declared in this scope; did you mean 'p'?
  105 |          ans = dp[sum];
      |                ^~
      |                p
snake_escaping.cpp:106:18: error: expected primary-expression before 'int'
  106 |          vector <int> v;
      |                  ^~~
snake_escaping.cpp:109:27: error: 'v' was not declared in this scope
  109 |           if(t[i] == '1') v.pb(p);
      |                           ^
snake_escaping.cpp:112:43: error: 'v' was not declared in this scope
  112 |          for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
      |                                           ^
snake_escaping.cpp:122:10: error: 'cout' was not declared in this scope
  122 |          cout << ans << '\n';
      |          ^~~~
snake_escaping.cpp:122:10: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?