Submission #1039301

#TimeUsernameProblemLanguageResultExecution timeMemory
1039301phongSnake Escaping (JOI18_snake_escaping)C++17
100 / 100
923 ms43332 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define ll long long const int nmax = 4e5 + 5, N = 1e5; const ll oo = 1e9; const int lg = 31, M = 2, mod = 1e6; #define pii pair<ll, ll> #define fi first #define se second #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n"; #define endl "\n" #define task "code" using namespace std; int L, q; string s; int F[1 << 20], G[1 << 20], cnt[1 << 20]; int bit(int msk, int x){ return msk>> x & 1; } main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); cin >> L >> q; cin >> s; for(int i = 0; i < (1 << L) ; ++i){ int c1 = 0, c2 = 0; for(int k = 1; k <= L; ++k){ if(bit(i, L - k)){ c1 += (1 << (k - 1)); } else c2 += (1 << (k - 1)); } cnt[c1] += s[i] - '0'; F[c1] += s[i] - '0'; G[c2] += s[i] - '0'; } for(int i = 0; i < L; ++i){ for(int msk = 0; msk < (1 << L); ++msk){ if(!bit(msk, i)){ F[msk ^ (1 << i)] += F[msk]; G[msk ^ (1 << i)] += G[msk]; } } } string tmp; vector<int> c0, c1, c2; while(q--){ cin >> tmp; c0.clear(); c1.clear();c2.clear(); for(int i = 0; i < L; ++i){ char x = tmp[i]; if(x == '0'){ c0.push_back(i); } else if(x == '1'){ c1.push_back(i); } else c2.push_back(i); } if((int)c1.size() <= 6){ // cout << "%"; int res = 0; for(auto p : c1) res += (1 << p); for(auto p : c2) res += (1 << p); ll ans = 0; for(int msk = 0; msk < (1 << c1.size()); ++msk){ int cur = res; for(int i = 0; i < c1.size(); ++i){ if(bit(msk, i)){ cur ^= (1 << c1[i]); } } int s = __builtin_popcount(msk); if(s & 1) ans -= F[cur]; else ans += F[cur]; } cout << ans << endl; } else if((int)c0.size() <= 6){ // cout << "?"; int res = 0; for(auto p : c0) res += (1 << p); for(auto p : c2) res += (1 << p); ll ans = 0; for(int msk = 0; msk < (1 << c0.size()); ++msk){ int cur = res; for(int i = 0; i < c0.size(); ++i){ if(bit(msk, i)){ cur ^= (1 << c0[i]); } } int s = __builtin_popcount(msk); if(s & 1) ans -= G[cur]; else ans += G[cur]; } cout << ans << endl; } else{ // cout << "#"; int res = 0; for(auto p : c1) res += (1 << p); int ans = 0; for(int msk = 0; msk < (1 << c2.size()); ++msk){ int cur = res; for(int i = 0; i < c2.size(); ++i){ if(bit(msk, i)){ cur ^= (1 << c2[i]); } } ans += cnt[cur]; } cout << ans << endl; } } } /* 3 5 12345678 000 0?? 1?0 ?11 ??? 3 1 12345678 ??? */

Compilation message (stderr)

snake_escaping.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for(int i = 0; i < c1.size(); ++i){
      |                                ~~^~~~~~~~~~~
snake_escaping.cpp:94:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for(int i = 0; i < c0.size(); ++i){
      |                                ~~^~~~~~~~~~~
snake_escaping.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for(int i = 0; i < c2.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...