Submission #1249309

#TimeUsernameProblemLanguageResultExecution timeMemory
1249309nvc2k8Snake Escaping (JOI18_snake_escaping)C++20
100 / 100
530 ms17664 KiB
#include <bits/stdc++.h> #define TASK "asdjasd" #define endl '\n' #define mp make_pair #define pb push_back #define fi first #define se second #define BIT(i,x) (((i)>>(x))&1) #define FOR(i,a,b) for(int i = (a); i<=(b); i++) #define FORD(i,a,b) for(int i = (a); i>=(b); i--) #define all(C) C.begin(), C.end() using namespace std; using ll = long long; using pii = pair<int,int>; const int INT_LIM = 2147483647; const ll LL_LIM = 9223372036854775807; template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;} template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;} ///------------------------------------------/// int n,q; char a[1<<20]; int dp[1<<20], dp2[1<<20]; void inp() { cin >> n >> q; FOR(i, 0, (1<<n)-1) { cin >> a[i]; a[i]-='0'; } } void solve() { FORD(t, n, 0) { FOR(mask, 0, (1<<n)-1) { if (t==n) dp[mask] = a[mask]; else { if (!BIT(mask, t)) dp[mask]+= dp[mask^(1<<t)]; } } FORD(mask, (1<<n)-1, 0) { if (t==n) dp2[mask] = a[mask]; else { if (BIT(mask, t)) dp2[mask]+= dp2[mask^(1<<t)]; } } } /// dp2[mask] : # mask2 | mask2_i <= mask_i /// dp[mask] : # mask2 | mask_i <= mask2_i FOR(t, 1, q) { string x; cin >> x; reverse(all(x)); int cnt1, cnt0, cntq, mask1, mask0, maskq, mask; cnt1 = cnt0 = cntq = mask1 = mask0 = maskq = mask = 0; FOR(i, 0, n-1) { if (x[i]=='?') { cntq++; maskq^=(1<<i); } else if (x[i]=='1') { cnt1++; mask1^=(1<<i); mask^=(1<<i); } else { cnt0++; mask0^=(1<<i); } } if (cntq<=6) { int ans = 0; for (int mask2 = maskq; mask2>0; mask2 = (mask2-1)&maskq) { ans+= a[mask^mask2]; } ans+= a[mask]; cout << ans << endl; continue; } if (cnt1<=6) { int ans = 0; mask^=maskq; for (int mask2 = mask1; mask2>0; mask2 = (mask2-1)&mask1) { if (__builtin_popcount(mask2)&1) ans-= dp2[mask^mask2]; else ans+= dp2[mask^mask2]; } ans+= dp2[mask]; cout << ans << endl; continue; } if (cnt0<=6) { int ans = 0; for (int mask2 = mask0; mask2>0; mask2 = (mask2-1)&mask0) { if (__builtin_popcount(mask2)&1) ans-= dp[mask^mask2]; else ans+= dp[mask^mask2]; } ans+= dp[mask]; cout << ans << endl; continue; } } } signed main() { ///--------------------------/// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(TASK".INP","r")!=NULL) { freopen(TASK".INP","r",stdin); freopen(TASK".OUT","w",stdout); } ///--------------------------/// int NTEST = 1; bool codeforces = 0; if (codeforces) cin >> NTEST; while (NTEST--) { inp(); solve(); } return 0; } ///------------------------------------------///

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(TASK".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...