Submission #896345

#TimeUsernameProblemLanguageResultExecution timeMemory
896345UnforgettableplSnake Escaping (JOI18_snake_escaping)C++17
75 / 100
2094 ms62784 KiB
//#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") /* ID: samikgo1 TASK: LANG: C++ */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef complex<ll> point; #define X real() #define Y imag() #define all(x) x.begin(),x.end() #define allr(x) x.rbegin(),x.rend() //#define f first //#define s second //#define x first //#define y second const ll INF = 1e17; const ll sqrtn = 440; const ll modulo = 1e9+7; const ll siz = 262144; const ll hashp = 923981238; const ll hashm = 932439994; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define int ll int memo[1594323]; char str[1048576]; char queries[1000001][20]; int ansq[1000001]; int get(char *s,int i){ if(memo[i]!=-1)return memo[i]; int p = 1; for(int x=0;x<13;x++) { if (s[x] == '?') { s[x] = '0'; int ans = get(s, i + p); s[x] = '1'; ans += get(s, i + 2 * p); s[x] = '?'; return memo[i] = ans; } p*=3; } } int getidx(const char *s){ int p = 1; int ans = 0; for(int a=0;a<13;a++){ if(s[a]=='0')ans+=p; else if(s[a]=='1')ans+=p*2; p*=3; } return ans; } inline bool match(string a,const char *b){ for(int i=0;i<7;i++)if(b[i]!='?' and a[i]!=b[i])return false; return true; } void solve() { int l,q; cin >> l >> q; for(int i=0;i<(1<<l);i++)cin >> str[i]; for(int i=0;i<(1<<l);i++)str[i]-='0'; for(int i=1;i<=q;i++){ string s;cin>>s; for(int x=0;x<20-l;x++)s.insert(s.begin(),'0'); for(int x=0;x<20;x++)queries[i][x] = s[x]; } for(int modifier=0;modifier<(1<<7);modifier++){ if((modifier<<13)>=(1<<l))break; string m = bitset<7>(modifier).to_string(); for(int&i:memo)i=-1; for(int i=0;i<(1<<13);i++)memo[getidx(bitset<13>(i).to_string().c_str())]=str[(modifier<<13)+i]; for(int i=1;i<=q;i++){ if(!match(m,queries[i]))continue; ansq[i]+=get(queries[i]+7,getidx(queries[i]+7)); } } for(int i=1;i<=q;i++)cout<<ansq[i]<<'\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("cses.fi.txt","r",stdin); // freopen(".out","w",stdout); // int t; // cin >> t; // while(t--) solve(); }

Compilation message (stderr)

snake_escaping.cpp: In function 'll get(char*, ll)':
snake_escaping.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^
#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...