Submission #1020258

#TimeUsernameProblemLanguageResultExecution timeMemory
1020258hqminhuwuSnake Escaping (JOI18_snake_escaping)C++14
100 / 100
536 ms39276 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int N = 5e5 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; int l, q, f[mask(20)], g[mask(20)], mul[2] = {1, -1}; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> l >> q >> s; forf (i, 0, s.size()){ f[i] = s[i] - '0'; g[i] = s[i] - '0'; } forf (i, 0, l){ forf (j, 0, mask(l)){ if (bit(j, i)){ f[j] += f[j ^ mask(i)]; } } } ford (i, l - 1, 0){ ford (j, mask(l) - 1, 0){ if (bit(j, i)) g[j ^ mask(i)] += g[j]; } } while (q--){ int fo = 0, fz = 0, fq = 0, res = 0; cin >> s; reverse(all(s)); forf (i, 0, l){ if (s[i] == '?') fq ^= mask(i); else if (s[i] == '0') fz ^= mask(i); else fo ^= mask(i); } if (bp(fz) <= 6){ //cout << fo << "\n"; for (int i = fz; ; i = (i - 1) & fz){ res += g[i | fo] * mul[bp(i) & 1]; //cout << g[i] << " " << mul[bp(i) & 1] << "\n"; if (i == 0) break; } } else if (bp(fo) <= 6){ for (int i = fo; ; i = (i - 1) & fo){ res += f[i | fq] * mul[(bp(fo) ^ bp(i)) & 1]; if (i == 0) break; } } else { for (int i = fq; ; i = (i - 1) & fq){ res += s[i | fo] - '0'; if (i == 0) break; } } cout << res << "\n"; } return 0; } /* */

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
snake_escaping.cpp:52:5: note: in expansion of macro 'forf'
   52 |     forf (i, 0, s.size()){
      |     ^~~~
#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...