Submission #396891

#	Time	Username	Problem	Language	Result	Execution time	Memory
396891		rqi	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	861 ms	65540 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

#define all(x) begin(x), end(x)

const int MOD = 1e9+7;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mx = 1000005;
int L, Q;
string S;
string T[mx];

// int three_pow[15];
// int three_sub[1594323];

// void smallL(){
//     three_pow[0] = 1;
//     for(int i = 1; i <= L; i++){
//         three_pow[i] = three_pow[i-1]*3;
//     }
//     for(int i = 0; i < three_pow[L]; i++){
//         int sub = i;
//         int sum = 0;
//         for(int j = 0; j < L; j++){
//             if(sub % 3 == 2){
//                 //cout << i << " " << i-2*three_pow[j] << " " << i-1*three_pow[j] << "\n";
//                 three_sub[i] = three_sub[i-2*three_pow[j]]+three_sub[i-1*three_pow[j]];
//                 sum = -1;
//                 break;
//             }
//             if(sub % 3 == 1){
//                 sum+=(1<<j);
//             }
//             sub/=3;
//         }
//         if(sum != -1){
//             three_sub[i] = S[sum]-'0';
//             //cout << i << " " << three_sub[i] << "\n";
//         }
//     }

//     //cout << "three_sub[2]: " << three_sub[8] << "\n";

//     for(int i = 1; i <= Q; i++){
//         int sub = 0;
//         for(int j = 0; j < L; j++){
//             if(T[i][j] == '1'){
//                 sub+=three_pow[j];
//             }
//             else if(T[i][j] == '?'){
//                 sub+=2*three_pow[j];
//             }
//         }
//         cout << three_sub[sub] << "\n";
//     }
// }

int trip[3][1<<20];

void genTrip(){
    for(int i = 0; i < (1<<L); i++){
        trip[2][i] = S[i]-'0';
    }
    for(int typ = 0; typ < 2; typ++){
        array<int, 1<<20> dp;
        array<int, 1<<20> ndp;
        for(int i = 0; i < (1<<20); i++){
            dp[i] = trip[2][i];
            ndp[i] = 0;
        }
        for(int j = 0; j < L; j++){
            for(int i = 0; i < (1<<L); i++){
                if((i>>j)&1){ //put in ?
                    ndp[i] = dp[i-(1<<j)]+dp[i];
                }
                else{
                    if(typ == 1){
                        ndp[i] = dp[i];
                    }
                    else{
                        ndp[i] = dp[i+(1<<j)];    
                    }
                }
            }
            swap(dp, ndp);
            for(int i = 0; i < (1<<L); i++){
                ndp[i] = 0;
            }
        }
        for(int i = 0; i < (1<<L); i++){
            bool is_odd = 0;
            for(int j = 0; j < L; j++){
                if((i>>j)&1){
                    is_odd^=1;
                }
            }
            if(is_odd){
                trip[typ][i] = -dp[i];
            }
            else{
                trip[typ][i] = dp[i];
            }
        }
    }
}

void printTrip(){
    map<char, int> from_char;
    from_char['0'] = 0;
    from_char['1'] = 1;
    from_char['?'] = 2;
    for(int i = 1; i <= Q; i++){
        vi typ_count(3, 0);
        for(auto u: T[i]){
            typ_count[from_char[u]]++;
        }
        int typ = -1;

        int min_typ_count = min(typ_count[0], min(typ_count[1], typ_count[2]));

        for(int i = 0; i < 3; i++){
            if(typ_count[i] == min_typ_count){
                typ = i;
                break;
            }
        }

        // cout << "typ: " << typ << "\n";

        // cout << trip[1][0] << "\n";

        int sub1 = 0; //positions of typ
        int sub2 = 0; //

        for(int j = 0; j < L; j++){
            int char_type = from_char[T[i][j]];
            if(char_type == typ){
                sub1+=(1<<j);
            }
            else{
                if(typ == 2){
                    if(char_type == 1){
                        sub2+=(1<<j);
                    }
                }
                else{
                    if(char_type == 2){
                        sub2+=(1<<j);
                    }
                }
            }
        }

        int res = 0;
        for(int i = sub1;;i = ((i-1)&sub1)){
            res+=trip[typ][i+sub2];
            // if(res >= MOD) res-=MOD;
            // if(res < 0) res+=MOD;
            if(i == 0) break;
        }

        if(typ != 2){
            bool is_odd = 0;
            for(auto u: T[i]){
                if(from_char[u] == 2 || from_char[u] == typ){
                    is_odd^=1;
                }
            }
            if(is_odd){
                res = -res;
                // if(res >= MOD) res-=MOD;
                // if(res < 0) res+=MOD;
            }
        }
        

        cout << res << "\n";

    }
    

    
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> L >> Q;
    cin >> S;
    for(int i = 1; i <= Q; i++){
        cin >> T[i];
        reverse(all(T[i]));
    }

    // if(L <= 13){
    //     smallL();
    //     exit(0);
    // }

    genTrip();
    printTrip();
}

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