Submission #1041945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041945		Zero_OP	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	427 ms	43508 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

int f(int n, int k){
    if(n == 1) return 1;
    if(k <= (n + 1) / 2){
        if(2 * k > n) return (2 * k) % n;
        else return 2 * k;
    }
    int rec = f(n / 2, k - (n + 1) / 2);
    if(n & 1) return 2 * rec + 1;
    else return 2 * rec - 1;
}


void testcase(){
    int L, q; string s;
    cin >> L >> q >> s;

    int n = 1 << L;
    vector<int> a(n), sos_submask(n), sos_supermask(n);
    for(int i = 0; i < n; ++i){
        a[i] = s[i] - '0';
        sos_submask[i] = a[i];
        sos_supermask[i] = a[i];
    }

    for(int i = 0; i < L; ++i){
        for(int mask = 0; mask < n; ++mask){
            if(mask >> i & 1) sos_submask[mask] += sos_submask[mask ^ (1 << i)];
            else sos_supermask[mask] += sos_supermask[mask ^ (1 << i)];
        }
    }

    int cnt[3], mask[3], BIG = (1 << L) - 1;
    while(q--){
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        memset(cnt, 0, sizeof(cnt));
        memset(mask, 0, sizeof(mask));
        for(int i = 0; i < L; ++i){
            int type = (t[i] == '0' ? 0 : (t[i] == '1' ? 1 : 2));
            ++cnt[type];
            mask[type] |= (1 << i);
        }

        int min_cnt = *min_element(cnt, cnt + 3);
        if(cnt[0] == min_cnt){
            int ans = 0;
            for(int s = mask[0];; s = (s - 1) & mask[0]){
                if(__builtin_popcount(s) & 1) ans -= sos_supermask[s | mask[1]];
                else ans += sos_supermask[s | mask[1]];
                if(!s) break;
            }
            cout << ans << '\n';
        } else if(cnt[1] == min_cnt){
            int ans = 0;
            for(int s = mask[1];; s = (s - 1) & mask[1]){
                if(__builtin_popcount(s) & 1) ans -= sos_submask[(mask[1] ^ s) | mask[2]];
                else ans += sos_submask[(mask[1] ^ s) | mask[2]];
                if(!s) break;
            }
            cout << ans << '\n';
        } else{
            int ans = 0;
            for(int s = mask[2];; s = (s - 1) & mask[2]){
                ans += a[mask[1] | s];
                if(!s) break;
            }
            cout << ans << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    int T = 1;
    //cin >> T;
    while(T--){
        testcase();
    }

    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void testcase()':
snake_escaping.cpp:56:26: warning: unused variable 'BIG' [-Wunused-variable]
   56 |     int cnt[3], mask[3], BIG = (1 << L) - 1;
      |                          ^~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:9:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:102:5: note: in expansion of macro 'file'
  102 |     file("task");
      |     ^~~~
snake_escaping.cpp:9:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:102:5: note: in expansion of macro 'file'
  102 |     file("task");
      |     ^~~~

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