Submission #1222785

#TimeUsernameProblemLanguageResultExecution timeMemory
1222785huudaiSnake Escaping (JOI18_snake_escaping)C++20
100 / 100
408 ms20852 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pii pair<int, int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back #define BIT(x,i) (((x)>>(i))&1) #define MASK(i) (1LL<<(i)) template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;} template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;} #define file "task" const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; const int oo = 1e9; const ll OO = 1e18; int n; int q; int a[MASK(20)]; int sosSub[MASK(20)]; int sosSuper[MASK(20)]; void input(){ cin >> n >> q; string st; cin >> st; for(int i = 0; i < MASK(n); i++) a[i] = st[i] - '0'; } void proc(){ for(int i = 0; i < MASK(n); i++){ sosSub[i] = sosSuper[i] = a[i]; } for(int i = 1; i <= n; i++){ for(int mask = 0; mask < MASK(n); mask++){ if(BIT(mask, i - 1)) sosSub[mask] += sosSub[mask ^ MASK(i - 1)]; else sosSuper[mask] += sosSuper[mask ^ MASK(i - 1)]; } } for(int i = 1; i <= q; i++){ string st; cin >> st; reverse(st.begin(), st.end()); int maskZero, maskOne, maskQues; maskZero = maskOne = maskQues = 0; for(int i = 0; i < n; i++){ if(st[i] == '0') maskZero |= MASK(i); if(st[i] == '1') maskOne |= MASK(i); if(st[i] == '?') maskQues |= MASK(i); } int ans = 0; if(__builtin_popcount(maskQues) <= 6){ for(int mask = maskQues; mask >= 0; mask = (mask - 1) & maskQues){ ans += a[mask | maskOne]; if(mask == 0) break; } } else if(__builtin_popcount(maskOne) <= 6){ //dem phan bu int sum = 0; for(int mask = (maskOne - 1) & maskOne; maskOne != 0 && mask >= 0; mask = (mask - 1) & maskOne){ if(__builtin_popcount(maskOne ^ mask) % 2) sum += sosSub[mask | maskQues]; else sum -= sosSub[mask | maskQues]; if(mask == 0) break; } ans = sosSub[maskOne | maskQues] - sum; } else{ // dem phan bu int sum = 0; for(int mask = maskZero; mask > 0; mask = (mask - 1) & maskZero){ if(__builtin_popcount(mask) % 2) sum += sosSuper[mask | maskOne]; else sum -= sosSuper[mask | maskOne]; } ans = sosSuper[maskOne] - sum; } cout << ans << '\n'; } } signed main(){ cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr); if(fopen(file".inp", "r")){ freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } input(); proc(); return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...