Submission #255642

#TimeUsernameProblemLanguageResultExecution timeMemory
255642egekabasSnake Escaping (JOI18_snake_escaping)C++14
5 / 100
2088 ms12824 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<ll, ll> pii; typedef pair<ld, ld> pld; ll l, q; string s; ll totzero = 0; ll a = 13, b = 5; ll sum[(1<<13)+10][(1<<7)+10]; ll p3[30]; //unordered_map<ll, ll> dp[23][(1<<13)+10]; ll v2; ll calc(ll step, ll idx, ll val){ /*if(dp[step][idx][val] != 0){ return dp[step][idx][val]-1; }*/ if(step == a || step == s.size()){ //dp[step][idx][val] = sum[idx][v2]+1; //return dp[step][idx][val]-1; return sum[idx][v2]; } //dp[step][idx][val] = 1; ll ret = 0; if(s[step] != '1') ret += calc(step+1, idx, val/3); //dp[step][idx][val] += calc(step+1, idx, val/3); if(s[step] != '0') ret += calc(step+1, idx+(1LL<<step), val/3); //dp[step][idx][val] += calc(step+1, idx+(1LL<<step), val/3); return ret; //return dp[step][idx][val]-1; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); p3[0] = 1; for(ll i = 1; i < 30; ++i) p3[i] = 3*p3[i-1]; cin >> l >> q; ll n = (1<<l); cin >> s; for(ll i = 0; i < n; ++i){ ll v1 = (i&((1<<a)-1)); for(ll bit = 0; bit < (1<<b); ++bit){ ll idx = 0; ll val = (i>>a); for(ll j = 0; j < b; ++j){ if((1<<j)&bit) idx += p3[j]*(val%2); else idx += p3[j]*2; val /= 2; } sum[v1][idx] += s[i]-'0'; } } for(ll i = 0; i < q; ++i){ cin >> s; reverse(s.begin(), s.end()); ll v1 = 0; for(ll i = 0; i < s.size(); ++i){ if(s[i] == '1') v1 += p3[i]; else if(s[i] == '?') v1 += 2*p3[i]; } v2 = 0; for(ll i = a; i < s.size(); ++i){ if(s[i] == '1') v2 += p3[i-a]; else if(s[i] == '?') v2 += 2*p3[i-a]; } cout << calc(0, 0, v1) << '\n'; } }

Compilation message (stderr)

snake_escaping.cpp: In function 'll calc(ll, ll, ll)':
snake_escaping.cpp:26:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(step == a || step == s.size()){
                     ~~~~~^~~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i = 0; i < s.size(); ++i){
                       ~~^~~~~~~~~~
snake_escaping.cpp:82:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i = a; i < s.size(); ++i){
                       ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...