제출 #334762

#제출 시각아이디문제언어결과실행 시간메모리
334762HoneyBadgerSnake Escaping (JOI18_snake_escaping)C++17
75 / 100
2065 ms25324 KiB
#include <iostream> #include <iomanip> #include <cstdio> #include <vector> #include <bitset> #include <string> #include <cstring> #include <map> #include <set> #include <stack> #include <queue> #include <deque> #include <utility> #include <algorithm> #include <random> #include <cmath> #include <cassert> #include <climits> #include <ctime> #include <chrono> #pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #ifdef LOCAL #define dbg(x) cout << #x << " : " << x << endl; #else #define dbg(x) #endif #define pb push_back #define ppb pop_back() #define mp make_pair #define fi(a, b) for (int i = a; i < b; i++) #define fj(a, b) for (int j = a; j < b; j++) #define fk(a, b) for (int k = a; k < b; k++) #define fi1(a, b) for (int i = a - 1; i >= b; i--) #define fj1(a, b) for (int j = a - 1; j >= b; j--) #define fk1(a, b) for (int k = a - 1; k >= b; k--) #define fx(x, a) for (auto& x : a) #define rep(i, a, b) for (int i = a; i < b; ++i) #define rep1(i, a, b) for (int i = a - 1; i >= b; --i) #define siz(x) (int)x.size() #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; } template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; } ostream& operator << (ostream &out, const vector<int> &b) { for (auto k : b) out << k << ' '; return out; } typedef long long ll; typedef long double ld; typedef char ch; typedef string str; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef vector<vpii> vvpii; typedef vector<ch> vch; typedef vector<vch> vvch; typedef vector<str> vs; const int MOD = 1000000007; const int INF = 1000000050; const long long BIG = (long long)2e18 + 50; const int MX = 1 << 20; const int PW = 20; const double EPS = 1e-9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int readChar(); inline int readInt(); inline void writeInt(int x, char end = 0); inline void writeChar(int x); static const int buf_size = 4096; inline int getChar() { static char buf[buf_size]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin); if (pos == len) return -1; return buf[pos++]; } inline int readChar() { int c = getChar(); while (c <= 32) c = getChar(); return c; } inline int readInt() { int c = readChar(); int x = 0; while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return x; } static int write_pos = 0; static char write_buf[buf_size]; inline void writeChar(int x) { if (write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0; write_buf[write_pos++] = x; } inline void writeInt(int x, char end) { char s[9]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) writeChar(s[n]); if (end) writeChar(end); } struct Flusher { ~Flusher() { if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; } } flusher; int n, q; int a[MX]; int sos1[MX]; int sos0[MX]; int bits[MX]; void calc() { for (int mask = 0; mask < (1 << n); ++mask) { sos1[mask] = a[mask]; sos0[mask] = a[mask]; bits[mask] = bits[mask >> 1] + (mask & 1); } for (int i = 0; i < n; ++i) { for (int mask = 0; mask < (1 << n); ++mask) { if ((mask >> i) & 1) { sos1[mask] += sos1[mask ^ (1 << i)]; } else { sos0[mask] += sos0[mask ^ (1 << i)]; } } } } int ans; str s; void solveq(int i = 0, int mask = 0) { if (i == n) { ans += a[mask]; return; } mask <<= 1; if (s[i] == '?') { solveq(i + 1, mask); solveq(i + 1, mask ^ 1); } else { solveq(i + 1, mask ^ (s[i] == '1')); } } void solve1(int i = 0, int mask = 0, int del = 0) { if (i == n) { if (del) ans -= sos1[mask]; else ans += sos1[mask]; return; } mask <<= 1; if (s[i] == '1') { solve1(i + 1, mask ^ 1, del); solve1(i + 1, mask, del ^ 1); } else { solve1(i + 1, mask ^ (s[i] == '?'), del); } } void solve0(int i = 0, int mask = 0, int del = 0) { if (i == n) { if (del) ans -= sos0[mask]; else ans += sos0[mask]; return; } mask <<= 1; if (s[i] == '0') { solve0(i + 1, mask ^ 1, del ^ 1); solve0(i + 1, mask, del); } else { solve0(i + 1, mask ^ (s[i] != '?'), del); } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); n = readInt(), q = readInt(); for (int i = 0; i < (1 << n); ++i) { a[i] = readChar() - '0'; } calc(); s = string(n, '0'); while (q--) { int pq = 0, p1 = 0, p0 = 0; fx(c, s) { c = readChar(); pq += c == '?'; p1 += c == '1'; p0 += c == '0'; } ans = 0; if (pq <= p1 && pq <= p0) { solveq(); } else if (p1 <= pq && p1 <= p0) { solve1(); } else { solve0(); } writeInt(ans, '\n'); } }
#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...