Submission #1113395

#TimeUsernameProblemLanguageResultExecution timeMemory
1113395vjudge1Snake Escaping (JOI18_snake_escaping)C++17
58 / 100
2063 ms39684 KiB
#include <bits/stdc++.h> #include <fstream> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define endl '\n' #define pb push_back #define INF 1000000000 #define fi first #define se second //#define cin fin //#define cout fout using namespace std; double const EPS = 1e-14; typedef long long ll; const ll P = 10007; const ll mod = 1e9 + 7; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key const int M = 2097152; ll dp1[M], dp0[M]; int main() { ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n, m; cin >> n >> m; string s; cin >> s; for(int i = 0; i < s.size(); i++) { dp1[i] = s[i]-'0'; dp0[i] = s[i]-'0'; } //int mx = 0; for(int j = 1; j < 21; j++) { for(int i = 0; i < M; i++) { if(((1<<(j-1))&i) > 0) { dp1[i] += dp1[(i^(1<<(j-1)))]; // mx = max((i^(1<<(j-1))),mx); } else { dp0[i] += dp0[(i^(1<<(j-1)))]; // mx = max((i^(1<<(j-1))),mx); } } } // cout << mx << 'p' << endl; while(m--) { string cur; cin >> cur; int cnt0 = 0, cnt1 = 0, cnt = 0; for(int i = 0; i < cur.size(); i++) { if(cur[i] == '0') cnt0++; else if(cur[i] == '1') cnt1++; else cnt++; } ll ans = 0; int siz = cur.size(); siz--; if(cnt <= 6) { for(int i = 0; i < (1<<cnt); i++) { int indx = 0; ll sum = 0; for(int j = cur.size()-1; j >= 0; j--) { if(cur[j] == '1') sum += (1<<(siz-j)); else if(cur[j] == '?' && (i&(1<<(indx++))) > 0) sum += (1<<(siz-j)); } // cout << sum << 'a' << endl; ans += s[sum]-'0'; } } else if(cnt1 <= 6) { for(int i = 0; i < (1<<cnt1); i++) { int indx = 0; ll sum = 0; int cn = 0; for(int j = cur.size()-1; j >= 0; j--) { if(cur[j] == '?') { sum += (1<<(siz-j)); } else if(cur[j] == '1') { if((i&(1<<(indx++))) > 0) sum += (1<<(siz-j)); else cn++; } } // cout << cn << ' ' << sum << ' ' << i << 'a' << endl; if(cn%2 == 0) ans += dp1[sum]; else ans -= dp1[sum]; } } else { for(int i = 0; i < (1<<cnt0); i++) { int indx = 0; ll sum = 0; int cn = 0; for(int j = cur.size()-1; j >= 0; j--) { if(cur[j] == '1') { sum += (1<<(siz-j)); } else if(cur[j] == '0' && (i&(1<<(indx++))) > 0) { sum += (1<<(siz-j)); cn++; } } // cout << cn << ' ' << sum << ' ' << i << 'a' << dp0[sum] << endl; if(cn%2 == 0) ans += dp0[sum]; else ans -= dp0[sum]; } } cout << ans << endl; } return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
snake_escaping.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i = 0; i < cur.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...