Submission #949619

#	Time	Username	Problem	Language	Result	Execution time	Memory
949619		ace5	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1060 ms	57052 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int maxn = 21;
const int maxsz = 1<<21;

int x[maxsz];
int sos[maxsz];
int soo[maxsz];
int dp[maxsz];
int dp2[maxsz];

int recq(int sv,int tpos,vector<int>& posq)
{
    if(tpos == posq.size())
    {
        return x[sv];
    }
    else
    {
        return recq(sv,tpos+1,posq) + recq(sv+(1<<posq[tpos]),tpos+1,posq);
    }
}
int rec0(int sv,int c0,int tpos,vector<int>& pos1)
{
    if(tpos == pos1.size())
    {
        return (c0%2 == 0 ? 1 : -1)*sos[sv];
    }
    else
    {
        return rec0(sv,c0+1,tpos+1,pos1) + rec0(sv+(1<<pos1[tpos]),c0,tpos+1,pos1);
    }
}
int rec1(int sv,int c1,int tpos,vector<int>& pos0)
{
    if(tpos == pos0.size())
    {
        return (c1%2 == 0 ? 1 : -1)*soo[sv];
    }
    else
    {
        return rec1(sv,c1,tpos+1,pos0) + rec1(sv+(1<<pos0[tpos]),c1+1,tpos+1,pos0);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    int sz = 1<<n;
    for(int j = 0;j < sz;++j)
    {
        char c;
        cin >> c;
        x[j] = c-'0';
    }
    for(int i = 0;i <= n;++i)
    {
        for(int j = 0;j < sz;++j)
        {
            if(i == 0)
            {
                dp[j] = x[j];
            }
            else
            {
                dp[j] = ((j&(1<<(i-1))) == 0 ? dp2[j] : dp2[j] + dp2[j^(1<<(i-1))]);
            }
        }
        for(int j = 0;j < sz;++j)
            dp2[j] = dp[j];
    }
    for(int i = 0;i < sz;++i)
    {
        sos[i] = dp[i];
    }
    for(int i = 0;i <= n;++i)
    {
        for(int j = 0;j < sz;++j)
        {
            if(i == 0)
            {
                dp[j] = x[j];
            }
            else
            {
                dp[j] = ((j&(1<<(i-1))) != 0 ? dp2[j] : dp2[j] + dp2[j^(1<<(i-1))]);
            }
        }
        for(int j = 0;j < sz;++j)
            dp2[j] = dp[j];
    }
    for(int i = 0;i < sz;++i)
    {
        soo[i] = dp[i];
    }
    while(q--)
    {
        vector<char> c(n);
        int c0 = 0,c1 = 0,cq = 0;
        for(int j = 0;j < n;++j)
        {
            cin >> c[j];
            if(c[j] == '?')
                cq++;
            else if(c[j] == '0')
                c0++;
            else
                c1++;
        }
        if(cq <= 6)
        {
            int sv = 0;
            vector<int> posq;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '?')
                    posq.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '1' ? 1 : 0);
            }
            cout << recq(sv,0,posq) << "\n";
        }
        else if(c0 <= 6)
        {
            int sv = 0;
            vector<int> pos0;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '0')
                    pos0.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '1' ? 1 : 0);
            }
            cout << rec1(sv,0,0,pos0) << "\n";
        }
        else
        {
            int sv = 0;
            vector<int> pos1;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '1')
                    pos1.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '?' ? 1 : 0);
            }
            cout << rec0(sv,0,0,pos1) << "\n";
        }
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int recq(int, int, std::vector<int>&)':
snake_escaping.cpp:16:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if(tpos == posq.size())
      |        ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int rec0(int, int, int, std::vector<int>&)':
snake_escaping.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(tpos == pos1.size())
      |        ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int rec1(int, int, int, std::vector<int>&)':
snake_escaping.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     if(tpos == pos0.size())
      |        ~~~~~^~~~~~~~~~~~~~

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