Submission #1050610

#TimeUsernameProblemLanguageResultExecution timeMemory
1050610vjudge1Snake Escaping (JOI18_snake_escaping)C++17
100 / 100
373 ms55120 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline") #include <bits/stdc++.h> #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma") using namespace std; // using namespace __gnu_pbds; // typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; #define static_assert(...); #include <tr2/dynamic_bitset> using custom_bitset = tr2::dynamic_bitset<__uint128_t>; #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define int long long #define bigInt __int128 #define dl double long #define fl float #define all(s) s.begin(), s.end() #define pub push_back #define puf push_front #define pob pop_back #define pof pob_front #define ins insert #define F first #define S second #define len length const int N = 100010; const int M = 1010; const int LN = 131072; const int INF = 1000000000000000000; const int MOD = 1e9 + 7; const int BLOCK = 500; int binpow(int a, int b, int MOD) { int res = 1; while (b > 0) { if (b & 1) { res = res * a; res %= MOD; } a = a * a; a %= MOD; b >>= 1; } return res; } int MMI(int a, int MOD) { int ret = binpow(a, MOD - 2, MOD); return ret; } // int mdiv(int a, int b) { // int ret = a*MMI(b); // ret %= MOD; // return ret; // } int mmul(int a, int b) { int ret = (a % MOD) * (b % MOD); ret %= MOD; return ret; } int madd(int a, int b) { int ret = (a % MOD) + (b % MOD); ret %= MOD; return ret; } int msub(int a, int b) { int ret = (a % MOD) - (b % MOD); ret += MOD; ret %= MOD; return ret; } int GCD(int a, int b) { if (b == 0) { return a; } return GCD(b, a % b); } int LCM(int a, int b) { return a*b / GCD(a, b); } struct pqComp { bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) const { return (p1.F < p2.F) || (p1.F == p2.F && p1.S < p2.S); } }; bool pCompF(pair<int, int>& p1, pair<int, int>& p2) { return p1.F < p2.F; } bool pCompS(pair<int, int>& p1, pair<int, int>& p2) { return p1.S < p2.S; } bool pCompFS(pair<int, int>& p1, pair<int, int>& p2) { return (p1.S < p2.S) || (p1.S == p2.S && p1.F < p2.F); } vector <pair<int, int>> DS {{1, 0}, {0, 1}};//{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};//, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; int n, q, a[11*N], sub[11*N], sup[11*N]; void solve() { cin >> n >> q; for (int i = 0; i < (1 << n); ++i) { char c; cin >> c; a[i] = (c - '0'); } for (int i = 0; i < (1 << n); ++i) { sub[i] = a[i]; sup[i] = a[i]; } for (int i = 0; i < n; ++i) { for (int mask = 0; mask < (1 << n); ++mask) { if (((mask >> i) & 1)) { sub[mask] += sub[mask - (1 << i)]; } } } for (int i = 0; i < n; ++i) { for (int mask = (1 << n) - 1; mask >= 0; --mask) { if (!((mask >> i) & 1)) { sup[mask] += sup[mask + (1 << i)]; } } } while (q--) { string s; cin >> s; int mask1 = 0, mask2 = 0, mask3 = 0; reverse(all(s)); for (int i = 0; i < n; ++i) { if (s[i] == '0') { mask1 |= (1 << i); } else if (s[i] == '1') { mask2 |= (1 << i); } else { mask3 |= (1 << i); } } int ans = 0, x = __builtin_popcount(mask1), y = __builtin_popcount(mask2), z = __builtin_popcount(mask3); if (z <= 6) { for (int mask = mask3; mask > 0; mask = (mask - 1) & mask3) { ans += a[(mask2 | mask)]; } ans += a[mask2]; } else if (y <= 6) { for (int mask = mask2; mask > 0; mask = (mask - 1) & mask2) { if ((__builtin_popcount(mask2) - __builtin_popcount(mask)) % 2) { ans -= sub[(mask | mask3)]; } else { ans += sub[(mask | mask3)]; } } if (__builtin_popcount(mask2) % 2) { ans -= sub[mask3]; } else { ans += sub[mask3]; } } else { for (int mask = mask1; mask > 0; mask = (mask - 1) & mask1) { if (__builtin_popcount(mask) % 2) { ans -= sup[(mask | mask2)]; } else { ans += sup[(mask | mask2)]; } } ans += sup[mask2]; } cout << ans << '\n'; } } signed main() { speed; int T = 1; //cin >> T; while (T--) { solve(); } } /* НЕ ЗАХОДИТ РЕШЕНИЕ? 1) ПРОВЕРЬ НА ОЧЕВИДНЫЕ ОШИБКИ В КОДЕ 2) ПРОВЕРЬ НА ПЕРЕПОЛНЕНИЯ 3) УБЕДИСЬ В ПРАВИЛЬНОСТИ АЛГОРИТМА */

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:138:22: warning: unused variable 'x' [-Wunused-variable]
  138 |         int ans = 0, x = __builtin_popcount(mask1), y = __builtin_popcount(mask2), z = __builtin_popcount(mask3);
      |                      ^
#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...