Submission #255174

#	Time	Username	Problem	Language	Result	Execution time	Memory
255174		Atill83	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	792 ms	65540 KiB

snake_escaping

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e6;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, l, q;
string s;
ll say[MAXN];
ll say2[MAXN];
ll ans[MAXN];
string qs[MAXN];

const int n37 = 2187;
const int n313 = 1594323;
int child[n313][2];
bool sub[n37][(1<<7)];
ll dp[n313];

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

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>l>>q;

    n = (1<<l);

    cin>>s;

    for(int i = 0; i < q; i++){
        cin>>qs[i];
        for(int j = 0; j < min(l, 7); j++){
            say[i] += (qs[i][j] == '?' ? 2 : qs[i][j] - '0');
            say[i] *= 3;
        }
        say[i] /= 3;
        for(int j = 7; j < l; j++){
            say2[i] += (qs[i][j] == '?' ? 2 : qs[i][j] - '0');
            say2[i] *= 3;
        }
        say2[i] /= 3;
    }

    for(int i = 0; i < n313; i++){
        int cur = i;
        child[i][0] = child[i][1] = -1;
        int cc = 1;
        for(int j = 0; j < 7; j++){
            if(cur % 3 == 2){
                child[i][0] = i - cc;
                child[i][1] = i - 2*cc;
                break;
            }
            cc *= 3;
            cur /= 3;
        }
    }


    for(int i = 0; i < n37; i++){
        for(int j = 0; j < (1<<7); j++){
            int cur1 = i, cur2 = j;
            bool tru = 1;
            for(int k = 0; k < 7; k++){
                if(cur1 % 3 != 2 && cur1 % 3 != cur2 % 2){
                    tru = 0;
                    break;
                }
                cur1 /= 3;
                cur2 /= 2;
            }
            sub[i][j] = tru;
        }
    }

    int rhs = max(0, l - 7);

    for(int j = 0; j < (1<<min(l, 7)); j++){
        
        for(int i = 0; i < n313; i++){
            if(child[i][0] == -1){
                int kal = 0;
                int cur = i;
                for(int k = 0; k < rhs; k++){
                    if(cur % 3) kal += (1<<k);
                    cur /= 3;
                }
                dp[i] = s[(j<<rhs) + kal] - '0';
            }else{
                dp[i] = dp[child[i][0]] + dp[child[i][1]];
            }
        }

        for(int i = 0; i < q; i++){
            if(!sub[say[i]][j]) continue;
            ans[i] += dp[say2[i]];
        }
    }

    for(int i = 0; i < q; i++) 
        cout<<ans[i]<<endl;


    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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