Submission #160817

#	Time	Username	Problem	Language	Result	Execution time	Memory
160817		combi1k1	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1085 ms	40512 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

int8_t  c[1 << 20];
string  s;

int f0[1 << 20];
int f1[1 << 20];

int work()  {
    int m0 = 0;
    int m1 = 0;
    int m2 = 0;

    int L = s.size();

    reverse(s.begin(),s.end());

    for(int i = 0 ; i < L ; ++i)    {
        if (s[i] == '0')    m0 |= (1 << i);
        if (s[i] == '1')    m1 |= (1 << i);
        if (s[i] == '?')    m2 |= (1 << i);
    }

    if (__builtin_popcount(m0) <= L / 3)    {
        int ans = f1[m1];
        for(int x = m0 ; x ; x = (x - 1) & m0)  {
            if (__builtin_popcount(x) & 1)
                ans -= f1[m1 | x];
            else
                ans += f1[m1 | x];
        }
        return  ans;
    }
    if (__builtin_popcount(m1) <= L / 3)    {
        int ans = f0[m0];
        for(int x = m1 ; x ; x = (x - 1) & m1)  {
            if (__builtin_popcount(x) & 1)
                ans -= f0[m0 | x];
            else
                ans += f0[m0 | x];
        }
        return  ans;
    }
    if (__builtin_popcount(m2) <= L / 3)    {
        int ans = c[m1];
        for(int x = m2 ; x ; x = (x - 1) & m2)
            ans += c[m1 | x];

        return  ans;
    }
}

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

    int n;  cin >> n;
    int q;  cin >> q;

    int m = (1 << n);

    cin >> s;

    for(int i = 0 ; i < m ; ++i)
        f0[m - i - 1] = f1[i] = c[i] = s[i] - '0';

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    if (j >> i & 1)
        f0[j ^ (1 << i)] += f0[j],
        f1[j ^ (1 << i)] += f1[j];

    for(int i = 0 ; i < q ; ++i)    {
        cin >> s;
        cout << work() << "\n";
    }
}
/*
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????
*/

Compilation message (stderr)

snake_escaping.cpp: In function 'int work()':
snake_escaping.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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