Submission #636057

#	Time	Username	Problem	Language	Result	Execution time	Memory
636057		Bruteforceman	Snake Escaping (JOI18_snake_escaping)	C++11	22 / 100	2077 ms	20108 KiB

snake_escaping

    #pragma GCC optimize("Ofast")
    #pragma GCC target("avx,avx2,fma")
    #include <bits/stdc++.h>
    #define taskname "test"
    #define fi first
    #define se second
    #define pb push_back
    #define faster ios_base::sync_with_stdio(0); cin.tie(0);
    using namespace std;
    using ll = long long;
    using ull = unsigned ll;
    using ld = long double;
    using pii = pair <int, int>;
    using pil = pair <int, ll>;
    using pli = pair <ll, int>;
    using pll = pair <ll, ll>;
    mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
     
    ll min(const ll &a, const ll &b){
        return (a < b) ? a : b;
    }
     
    ll max(const ll &a, const ll &b){
        return (a > b) ? a : b;
    }
     
    //const ll Mod = 1000000007;
    //const ll Mod2 = 999999999989;
    //only use when required
    const int maxN = 20;
     
    int n, q;
    string s, t;
    int dp[(1 << maxN) + 5];
    int f[(1 << maxN) + 5];
     
    void WriteInt(int x)
    {
        if (x > 9)
            WriteInt(x / 10);
        putchar(x % 10 + '0');
    }
     
    inline int inv(int i){
        return ((1 << n) - 1) ^ i;
    }
     
     
    void Init(){
        cin >> n >> q >> s;
        for (int i = 0; i < int(s.length()); ++i){
            dp[i] = s[i] - '0';
            f[inv(i)] = dp[i];
        }
        for (int i = 0; i < n; ++i){
            for (int j = 1; j < 1 << n; ++j){
                if (j & (1 << i)){
                    dp[j] += dp[j ^ (1 << i)];
                }
            }
        }
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < 1 << n; ++j){
                if (j & (1 << i)){
                    f[j] += f[j ^ (1 << i)];
                }
            }
        }
        int x, y, z;
        int mask1, mask0, tem;
        while (q--){
            cin >> t;
            x = y = z = mask1 = mask0 = tem = 0;
            vector <int> val((1 << n) + 1, 0);
            reverse(t.begin(), t.end());
            for (int i = 0; i < n; ++i){
                if (t[i] == '0') ++x, mask0 ^= 1 << i;
                if (t[i] == '1') ++y, mask1 ^= 1 << i;
                if (t[i] == '?') ++z, tem ^= 1 << i;
            }
            if (z == min(min(x, y), z)){
                //brute all ?s
                int ans = s[mask1] - '0';
                for (int i = tem; i; i = (i - 1) & tem){
                    ans += s[i + mask1] - '0';
                }
                WriteInt(ans);
                putchar('\n');
            }
            else if (x == min(x, y)){
                int ans = -f[tem];
                for (int i = mask0; i; i = (i - 1) & mask0){
                    bool cnt = __builtin_parity(i);
                    if (cnt) ans += f[i + tem];
                    else ans -= f[i + tem];
                }
                ans = abs(ans);
                WriteInt(ans);
                putchar('\n');
            }
            else{
                int ans = -dp[tem];
                for (int i = mask1; i; i = (i - 1) & mask1){
                    bool cnt = __builtin_parity(i);
                    if (cnt) ans += dp[i + tem];
                    else ans -= dp[i + tem];
                }
                ans = abs(ans);
                WriteInt(ans);
                putchar('\n');
            }
        }
    }
     
     
    int main(){
        if (fopen(taskname".inp", "r")){
            freopen(taskname".inp", "r", stdin);
            //freopen(taskname".out", "w", stdout);
        }
        faster;
        ll tt = 1;
        //cin >> tt;
        while (tt--){
            Init();
        }
    }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:118:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |             freopen(taskname".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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