oj.uz

Submission #680159

# Submission time Handle Problem Language Result Execution time Memory
680159 2023-01-10T03:34:52 Z Duy_e Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 23344 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 (1) {
            ll ans = 0;
            for (int i = mc; ; i = (i - 1) & mc) {
                ans += a[i ^ ma];
                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
5.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 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.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 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 214 ms 4808 KB Output is correct
12 Correct 221 ms 4624 KB Output is correct
13 Correct 177 ms 3724 KB Output is correct
14 Correct 178 ms 3956 KB Output is correct
15 Correct 236 ms 4756 KB Output is correct
16 Correct 204 ms 4128 KB Output is correct
17 Correct 197 ms 3916 KB Output is correct
18 Correct 1273 ms 5880 KB Output is correct
19 Correct 173 ms 2816 KB Output is correct
20 Correct 251 ms 4456 KB Output is correct

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 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 214 ms 4808 KB Output is correct
12 Correct 221 ms 4624 KB Output is correct
13 Correct 177 ms 3724 KB Output is correct
14 Correct 178 ms 3956 KB Output is correct
15 Correct 236 ms 4756 KB Output is correct
16 Correct 204 ms 4128 KB Output is correct
17 Correct 197 ms 3916 KB Output is correct
18 Correct 1273 ms 5880 KB Output is correct
19 Correct 173 ms 2816 KB Output is correct
20 Correct 251 ms 4456 KB Output is correct
21 Correct 354 ms 5024 KB Output is correct
22 Correct 390 ms 5200 KB Output is correct
23 Correct 205 ms 4152 KB Output is correct
24 Correct 207 ms 4172 KB Output is correct
25 Correct 449 ms 5984 KB Output is correct
26 Correct 245 ms 4520 KB Output is correct
27 Correct 244 ms 4364 KB Output is correct
28 Execution timed out 2020 ms 2112 KB Time limit exceeded
29 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 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 145 ms 22208 KB Output is correct
12 Correct 263 ms 23344 KB Output is correct
13 Correct 80 ms 22972 KB Output is correct
14 Correct 91 ms 23028 KB Output is correct
15 Correct 584 ms 23108 KB Output is correct
16 Correct 91 ms 23092 KB Output is correct
17 Correct 92 ms 23036 KB Output is correct
18 Execution timed out 2074 ms 22236 KB Time limit exceeded
19 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 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 214 ms 4808 KB Output is correct
12 Correct 221 ms 4624 KB Output is correct
13 Correct 177 ms 3724 KB Output is correct
14 Correct 178 ms 3956 KB Output is correct
15 Correct 236 ms 4756 KB Output is correct
16 Correct 204 ms 4128 KB Output is correct
17 Correct 197 ms 3916 KB Output is correct
18 Correct 1273 ms 5880 KB Output is correct
19 Correct 173 ms 2816 KB Output is correct
20 Correct 251 ms 4456 KB Output is correct
21 Correct 354 ms 5024 KB Output is correct
22 Correct 390 ms 5200 KB Output is correct
23 Correct 205 ms 4152 KB Output is correct
24 Correct 207 ms 4172 KB Output is correct
25 Correct 449 ms 5984 KB Output is correct
26 Correct 245 ms 4520 KB Output is correct
27 Correct 244 ms 4364 KB Output is correct
28 Execution timed out 2020 ms 2112 KB Time limit exceeded
29 Halted 0 ms 0 KB -