Submission #1105684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105684		FucKanh	Snake Escaping (JOI18_snake_escaping)	C++11	100 / 100	1081 ms	54444 KiB

snake_escaping

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

const int BIT = 20;

int f[1<<BIT], g[1<<BIT], h[1<<BIT], ans;

void solve2(int i, vector<int> &v, int val) {
    if (i==v.size()) {
        ans += h[val];
        return;
    }
    val &= ~(1<<v[i]);
    solve2(i+1,v,val);
    val |= (1<<v[i]);
    solve2(i+1,v,val);
}

void solve1(int i, vector<int> &v, int val, int cnt) {
    if (i==v.size()) {
        if (cnt==0) return;
        if (cnt%2) {
            ans -= f[val];
        }
        else {
            ans += f[val];
        }
        return;
    }
    val |= (1<<v[i]);
    solve1(i+1,v,val,cnt);
    val &= ~(1<<v[i]);
    solve1(i+1,v,val,cnt+1);
}

void solve0(int i, vector<int> &v, int val, int cnt) {
    if (i==v.size()) {
        if (cnt==0) return;
        if (cnt%2) {
            ans -= g[val];
        }
        else {
            ans += g[val];
        }
        return;
    }
    val |= (1<<v[i]);
    solve0(i+1,v,val,cnt+1);
    val &= ~(1<<v[i]);
    solve0(i+1,v,val,cnt);
}

void solve() {
    int n,q; cin >> n >> q;
    for (int i =0; i < (1<<n); i++) {
        char c; cin >> c;
        f[i] += c - '0';
        g[i] += c - '0';
        h[i] += c - '0';
//        cerr << "cin >> " << bitset<5>(i) << " :" << c << endl;
    }
    for (int i = 0; i < n; i++) {
        for (int x = 0; x < (1<<n); x++) {
            if (x&(1<<i)) f[x] += f[x^(1<<i)];
            else g[x] += g[x^(1<<i)];
        }
    }

    for (int i = 0; i < q; i++) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        int cnt = 0, val = 0, val2 = 0,val1 = 0;
        vector<int> v1,v2,v0;
        for (char c : s) {
            if (c!='0') {
                val |= (1<<cnt);
                if (c=='1') {
                    val2 |= (1<<cnt);
                    v1.push_back(cnt);
                }
                else {
                    v2.push_back(cnt);
                    val1 |= (1<<cnt);
                }
            }
            else {
                v0.push_back(cnt);
            }
            cnt++;
        }
        if (v2.size() <= v1.size() && v2.size() <= v0.size()) {
            ans = 0;
            solve2(0,v2,val);
        }
        else if (v1.size() <= v2.size() && v1.size() <= v0.size()) {
            ans = f[val];
            solve1(0,v1,val,0);
        }
        else {
            ans = g[val2];
            solve0(0,v0,val2,0);
        }
        cout << ans << '\n';
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve2(long long int, std::vector<long long int>&, long long int)':
snake_escaping.cpp:13:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (i==v.size()) {
      |         ~^~~~~~~~~~
snake_escaping.cpp: In function 'void solve1(long long int, std::vector<long long int>&, long long int, long long int)':
snake_escaping.cpp:24:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (i==v.size()) {
      |         ~^~~~~~~~~~
snake_escaping.cpp: In function 'void solve0(long long int, std::vector<long long int>&, long long int, long long int)':
snake_escaping.cpp:41:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (i==v.size()) {
      |         ~^~~~~~~~~~

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