Submission #1099076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099076		trie	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	584 ms	39152 KiB

snake_escaping

// opt
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;

template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}

template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}

const int N = 1e5 + 5;
const int V = 1e6 + 5;
const int MOD = 1e9 + 7;

int n, q, cost[MASK(20) + 5], f[MASK(20) + 5];
string s;

void solve() {
	cin >> n >> q;
	cin >> s;

	for(int i = 0 ; i < (1 << n) ; i++) f[i] = cost[i] = (s[i] - '0');

	for(int i = 0 ; i < n ; i++)
		for(int mask = 0 ; mask < MASK(n) ; mask++)
			if (getbit(mask, i)) cost[mask] += cost[mask ^ MASK(i)];

    for(int i = 0 ; i < n ; i++)
        for(int mask = 0 ; mask < MASK(n) ; mask++)
            if (!getbit(mask, i)) f[mask] += f[mask | MASK(i)];

	for(int i = 0 ; i < q ; i++) {
		string t;	cin >> t;
		int mask1, mask2, mask3, sz = (int) t.size() - 1;
		ll ans;
		mask1 = mask2 = mask3 = ans = 0;

		for(int i = sz ; i >= 0 ; i--)
			if (t[i] == '1') mask1 |= MASK(sz - i);
			else if (t[i] == '?') mask2 |= MASK(sz - i);
            else mask3 |= MASK(sz - i);

        if (cntbit(mask1) <= 6) {
            int c = cntbit(mask1) & 1;
            for(int submask = mask1 ; submask >= 0 ; submask = (submask - 1) & mask1) {
                if ((cntbit(submask) & 1) == c) ans += cost[submask + mask2];
                else ans -= cost[submask + mask2];
                if (submask == 0) break;
            }
        } else if (cntbit(mask2) <= 6) {
            for(int submask = mask2 ; submask >= 0 ; submask = (submask - 1) & mask2) {
                ans += (s[submask + mask1] - '0');
                if (submask == 0) break;
            }
        } else {
            for(int submask = mask3 ; submask >= 0 ; submask = (submask - 1) & mask3) {
                if (cntbit(submask) & 1) ans -= f[submask + mask1];
                else ans += f[submask + mask1];
                if (submask == 0) break;
            }
        }

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

int main(void) {
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int t = 1; while(t--) solve();
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |     for(int i = 0 ; i < n ; i++)
      |     ^~~
snake_escaping.cpp:46:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |  for(int i = 0 ; i < q ; i++) {
      |  ^~~
snake_escaping.cpp:53:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |    if (t[i] == '1') mask1 |= MASK(sz - i);
      |                                   ~~~^~~
snake_escaping.cpp:15:23: note: in definition of macro 'MASK'
   15 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:54:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |    else if (t[i] == '?') mask2 |= MASK(sz - i);
      |                                        ~~~^~~
snake_escaping.cpp:15:23: note: in definition of macro 'MASK'
   15 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:55:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   55 |             else mask3 |= MASK(sz - i);
      |                                ~~~^~~
snake_escaping.cpp:15:23: note: in definition of macro 'MASK'
   15 | #define MASK(i) (1 << i)
      |                       ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25