oj.uz

Submission #680156

# Submission time Handle Problem Language Result Execution time Memory
680156 2023-01-10T03:31:25 Z Duy_e Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 2e6 + 5;

int a[N], L, q, n;

ll dp[2][N];

// dp[bit][mask] = sum of mask such bit on = bit

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        // freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    
    cin >> L >> q;  
    n = 1 << L;

    rep(i, 0, n - 1) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }

    rep(bit, 0, 1) {
        rep(mask, 0, n - 1) dp[bit][mask] = a[bit == 0 ? (n - 1 - mask) : mask];
        rep(i, 0, L - 1) rep(mask, 0, n - 1) 
            if (mask >> i & 1)
                dp[bit][mask] += dp[bit][mask ^ (1 << i)];
        // rep(mask, 0, n - 1)
        //cout << bit << ' ' << mask << ": " << dp[bit][mask] << '\n';
    }   

    //return 0;
    string s;

    while (q --) {
        int na = 0, nb = 0, nc = 0, ma = 0, mb = 0, mc = 0;
        cin >> s;
        reverse(s.begin(), s.end());

        rep(i, 0, L - 1) {
            if (s[i] == '1') {
                na ++; ma ^= 1 << i;
            }

            if (s[i] == '0') {
                nb ++; mb ^= 1 << i;
            }

            if (s[i] == '?') {
                nc ++; mc ^= 1 << i;
            }
        }

        if (nc <= na && nc <= nb) {
            ll ans = 0;
            for (int i = mc; ; i = (i - 1) & mc) {
                ans += a[i];
                if (i == 0) break;
            }            

            cout << ans << '\n';
        } else {
            int bit = 1, mask = ma, other = mb;
            if (nb < na) {
                bit = 0;
                mask = mb;
                other = ma;
            }

            ll ans = 0;
            for (int i = mask; ; i = (i - 1) & mask) {
                if (__builtin_popcount(i) & 1)
                    ans -= dp[bit][i ^ mc];
                else    
                    ans += dp[bit][i ^ mc];

                if (i == 0) break;
            }

            cout << ans << '\n';
        }
    }

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮

3 case
cnt 0 min
cnt 1 min
cnt ? min

-> handle each case in 2^cnt, cnt <= L / 3 -> O(q * 2 ^ (L / 3));

**/

Compilation message

snake_escaping.cpp:97:9: warning: "/*" within comment [-Wcomment]
   97 | /**  /\_/\
      |          
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:74:37: warning: variable 'other' set but not used [-Wunused-but-set-variable]
   74 |             int bit = 1, mask = ma, other = mb;
      |                                     ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -