제출 #1247638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247638		nh0902	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	320 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

//#define int long long

const int N = (1 << 20);

const int M = 1e5 + 10;

const int inf = 1e18;

int L, b, q, s[N];

int dp0[N], dp1[N], cnt[N], cur[N];

int si[2] = {1, - 1};

void prep() {
    cin >> L >> q;
    b = 1 << L;
    char c;
    for (int i = 0; i < b; i ++) {
        cin >> c;
        s[i] = c - '0';
    }

    for (int i = 0; i < b; i ++) {
        dp0[i] = s[i];
        dp1[i] = s[b - i];
    }

    for (int i = 0; i < L; i ++) {
        for (int x = 0; x < b; x ++) {
            if ((x >> i) & 1) {
                int y = x ^ (1 << i);
                dp0[x] += dp0[y];
                dp1[x] += dp1[y];
            }
        }
    }

    for (int i = 0; i < b; i ++) {
        //cout << i << " : " << dp0[i] << "\n";
    }

}


char c[21];

int query(int pos, int cur) {
    if (pos == L) {
        return s[cur];
        //cout << cur << "\n";
    }

    if (c[pos] == '0') return query(pos + 1, cur);
    if (c[pos] == '1') return query(pos + 1, cur + (1 << pos));

    return query(pos + 1, cur) + query(pos + 1, cur + (1 << pos));
}

int query0(int pos, int cur) {
    if (pos == L) {
        //cout << cur << "\n";
        return dp0[cur];
    }

    if (c[pos] == '0') return query0(pos + 1, cur);
    if (c[pos] == '?') return query0(pos + 1, cur + (1 << pos));

    return query0(pos + 1, cur + (1 << pos)) - query0(pos + 1, cur);
}

int query1(int pos, int cur) {
    if (pos == L) return dp1[cur];

    if (c[pos] == '1') return query1(pos + 1, cur);
    if (c[pos] == '?') return query1(pos + 1, cur + (1 << pos));

    return query1(pos + 1, cur + (1 << pos)) - query1(pos + 1, cur);
}

void solve() {

    while (q --) {

        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (int i = L - 1; i >= 0; i --) {
            cin >> c[i];
            if (c[i] == '0') cnt0 ++;
            else if (c[i] == '1') cnt1 ++;
            else cnt2 ++;


        }

        int ans = 0;

        if (cnt2 <= L / 3) ans = query(0, 0);
        else if (cnt1 <= L / 3) ans = query0(0, 0);
        else ans = query1(0, 0);

        cout << ans << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp:11:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int inf = 1e18;
      |                 ^~~~

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