Submission #1219063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219063		nmhung	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	495 ms	37260 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
//#define in ({int x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})

#define bit(i, mask) (((mask) >> (i)) & 1)
#define on(i, mask) ((mask) | (1LL << (i)))
#define off(i, mask) ((mask) & (~(1LL << (i))))

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define plx pair<ll, int>
#define vi vector<int>
#define vvi vector<vi>
#define all(a) (a).begin(), (a).end()
#define len(x) ((int)(x).size())
#define pb push_back
#define endl '\n'
#define ub(x, i) upper_bound(all(x), i) - x.begin()
#define lb(x, i) lower_bound(all(x), i) - x.begin()

#define name "snakes"

template<typename T1, typename T2> bool mini(T1 &a, T2 b)
    {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b)
    {if(a < b) a = b; else return 0; return 1;}

const int mod = 1e9+7;
const int inf = 1e9+9;
const ll oo = 1e18l+7;
const int M = 5e5+6;
const int N = 2e6+7;
const int LOG = 31 - __builtin_clz(N);

int k, q, a[N];
ll sign[N], f[N], g[N];

void inp(){
    cin >> k >> q;
    string s; cin >> s;
    for(int i = 0; i < (1 << k); i++) a[i] = s[i] - '0';
}

void proc(){
    for(int i = 0; i < (1 << k); i++) sign[i] = (__builtin_popcount(i) & 1) ? -1 : 1;
    for(int i = 0; i < (1 << k); i++){
        f[i] = a[i];
        g[i] = a[(1 << k) - 1 - i];
    }
    for(int i = 0; i < k; i++){
        for(int mask = 0; mask < (1 << k); mask++){
            if(bit(i, mask)){
                f[mask] += f[mask ^ (1 << i)];
                g[mask] += g[mask ^ (1 << i)];
            }
        }
    }

    while(q--){
        string s; cin >> s;
        reverse(all(s));
        int c0 = 0, c1 = 0, cq = 0;
        int m0 = 0, m1 = 0, mq = 0;
        for (int i = 0; i < k; i++) {
            if (s[i] == '0') c0++, m0 |= (1 << i);
            else if (s[i] == '1') c1++, m1 |= (1 << i);
            else cq++, mq |= (1 << i);
        }

        ll res = 0;
        if(cq <= 7){
            for(int mask = mq; ; mask = (mask - 1) & mq){
                res += a[mask | m1];
                if(mask == 0) break;
            }
        }
        else if(c1 <= 6){
            for(int mask = m1; ; mask = (mask - 1) & m1){
                res += sign[m1 ^ mask] * f[mask | mq];
                if(mask == 0) break;
            }
        }
        else{
            for(int mask = m0; ; mask = (mask - 1) & m0){
                res += sign[m0 ^ mask] * g[mask | mq];
                if(mask == 0) break;
            }
        }
        cout << res << endl;
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    rf

    int test = 1;
    //cin >> test;

    while(test--){
        inp();
        proc();
    }

    cerr << "Time elapsed: " << TIME << "s" << endl;
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:8:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:104:5: note: in expansion of macro 'rf'
  104 |     rf
      |     ^~
snake_escaping.cpp:8:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:104:5: note: in expansion of macro 'rf'
  104 |     rf
      |     ^~

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