Submission #391459

#	Time	Username	Problem	Language	Result	Execution time	Memory
391459		iANikzad	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1190 ms	19524 KiB

snake_escaping

#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;

int solve_a() 
{
    int ans = 0, base = 0, mask = 0;
    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';
  
    return ans;
}
 
int solve_b() 
{
    int ans = 0, base = 0, mask = 0;
    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;
}
 
int solve_c() 
{ 
    int ans = 0, base = 0, mask = 0;
    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];
  
    return ans;
}

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

    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) cout << solve_a() << "\n";
        else if(b < 7) cout << solve_b() << "\n";
        else cout << solve_c() << "\n";
    }
  
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:95:13: warning: unused variable 'ans' [-Wunused-variable]
   95 |         int ans = 0, base = 0, mask = 0;
      |             ^~~
snake_escaping.cpp:95:22: warning: unused variable 'base' [-Wunused-variable]
   95 |         int ans = 0, base = 0, mask = 0;
      |                      ^~~~
snake_escaping.cpp:95:32: warning: unused variable 'mask' [-Wunused-variable]
   95 |         int ans = 0, base = 0, mask = 0;
      |                                ^~~~

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