oj.uz

Submission #334747

# Submission time Handle Problem Language Result Execution time Memory
334747 2020-12-10T00:18:22 Z HoneyBadger Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 27328 KB 
#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 int long long
#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 unsigned long long ull;
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());


int n, q;
int a[MX];
int sos1[MX];
int sos0[MX];

void calc() {
    for (int mask = 0; mask < (1 << n); ++mask) {
        sos1[mask] = a[mask];
        sos0[mask] = a[mask];
    }
    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;
    }
    if (s[i] == '?') {
        solveq(i + 1, mask * 2);
        solveq(i + 1, mask * 2 + 1);
    } else {
        solveq(i + 1, mask * 2 + (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;
    }
    if (s[i] == '1') {
        solve1(i + 1, mask * 2 + 1, del);
        solve1(i + 1, mask * 2, del ^ 1);  
    } else {
        solve1(i + 1, mask * 2 + (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;
    }
    if (s[i] == '0') {
        solve0(i + 1, mask * 2 + 1, del);
        solve0(i + 1, mask * 2, del ^ 1);
    } else {
        solve0(i + 1, mask * 2 + (s[i] != '?'), del);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }

    calc();
    
    while (q--) {
        cin >> s;
        int pq = 0, p1 = 0, p0 = 0;
        fx(c, s) {
            pq += c == '?';
            p1 += c == '1';
            p0 += c == '0';
        }
        ans = 0;
        solveq();
        /*if (pq <= n / 3) {
            solveq();
        } else if (p1 <= n / 3) {
            solve1();
        } else {    
            solve0();
        }*/
        cout << ans << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 542 ms 6320 KB Output is correct
12 Correct 747 ms 6084 KB Output is correct
13 Correct 304 ms 5228 KB Output is correct
14 Correct 286 ms 5364 KB Output is correct
15 Correct 731 ms 6380 KB Output is correct
16 Correct 429 ms 5484 KB Output is correct
17 Correct 445 ms 5504 KB Output is correct
18 Execution timed out 2078 ms 4876 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 542 ms 6320 KB Output is correct
12 Correct 747 ms 6084 KB Output is correct
13 Correct 304 ms 5228 KB Output is correct
14 Correct 286 ms 5364 KB Output is correct
15 Correct 731 ms 6380 KB Output is correct
16 Correct 429 ms 5484 KB Output is correct
17 Correct 445 ms 5504 KB Output is correct
18 Execution timed out 2078 ms 4876 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 752 ms 27328 KB Output is correct
12 Correct 1544 ms 27252 KB Output is correct
13 Correct 161 ms 27244 KB Output is correct
14 Correct 284 ms 27244 KB Output is correct
15 Execution timed out 2048 ms 26812 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 542 ms 6320 KB Output is correct
12 Correct 747 ms 6084 KB Output is correct
13 Correct 304 ms 5228 KB Output is correct
14 Correct 286 ms 5364 KB Output is correct
15 Correct 731 ms 6380 KB Output is correct
16 Correct 429 ms 5484 KB Output is correct
17 Correct 445 ms 5504 KB Output is correct
18 Execution timed out 2078 ms 4876 KB Time limit exceeded
19 Halted 0 ms 0 KB -