oj.uz

Submission #391448

# Submission time Handle Problem Language Result Execution time Memory
391448 2021-04-18T19:04:31 Z iANikzad Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 3 ms 332 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 20;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int sos[1 << 20], rsos[1 << 20];

string s, k;
int l, q;
int a, b, c;

int32_t main()
{
    FAST;

    cin >> l >> q >> s;

    for(int i = 0; i < (1 << l); i++)
        sos[i] = s[i] - '0', rsos[i] = s[(1 << l) - i - 1] - '0';

    for(int i = 0; i < l; i++) 
        for(int mask = 0; mask < (1 << l); mask++)
            if(mask & (1 << i))
                sos[mask] += sos[mask ^ (1 << i)], rsos[mask] += rsos[mask ^ (1 << i)];

    while(q--)
    {
        cin >> k;
        reverse(all(k));

        a = b = c = 0;
        int ans = 0, base = 0, mask = 0;

        for(int i = 0; i < l; i++)
        {
            if(k[i] == '?') a++;
            if(k[i] == '0') b++;
            if(k[i] == '1') c++;
        }

        if(a < 7)
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '?') mask += 1 << i;
                else if (k[i] == '1') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += s[i | base] - '0';
            ans += s[base] - '0';
        }
        else if(b < 7)
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '0') mask += 1 << i;
                else if (k[i] == '?') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += ((b - __builtin_popcount(i)) & 1 ? -1 : 1) * rsos[i | base];
            ans += (b & 1 ? -1 : 1) * rsos[base];

            return ans;
         
        }
        else
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '1') mask += 1 << i;
                else if (k[i] == '?') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += ((c - __builtin_popcount(i)) & 1 ? -1 : 1) * sos[i | base];
            ans += (c & 1 ? -1 : 1) * sos[base];

        }

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

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -