oj.uz

답안 #255684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255684 2020-08-01T14:23:05 Z egekabas Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 2 ms 1152 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll l, q;
string s;
ll a = 8, b = 3;
ll sum[(1<<10)+10][(1<<7)+10];
ll p3[30];
unordered_map<ll, ll> dp[(1<<10)+10];
ll v2;
ll n;
ll calc(ll step, ll idx, ll val){
    if(dp[idx][val] != 0){ 
        return dp[idx][val]-1;
    }
    if(idx >= n){
        //cout << s << '\n' << idx << '\n';
        dp[idx][val] = sum[idx-(1<<a)][v2]+1;
        return dp[idx][val]-1;
    }
    dp[idx][val] = 1;
    if(val/p3[step] != 1)
        dp[idx][val] += calc(step-1, idx*2, val%p3[step]);
    if(val/p3[step] != 0)
        dp[idx][val] += calc(step-1, idx*2+1, val%p3[step]);
    
    return dp[idx][val]-1;
}
map<ll, ll> mpp;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    p3[0] = 1;
    for(ll i = 1; i < 30; ++i)
        p3[i] = 3*p3[i-1];
    cin >> l >> q;
    a = min(a, l);

    n = (1<<l);
    cin >> s;
    ll cur = (1<<a);
    for(ll i = 0; i < n; ++i){
        if(mpp[i&((1<<a)-1)] == 0) mpp[i&((1<<a)-1)] = cur++;
        ll v1 = mpp[i&((1<<a)-1)];

        for(ll bit = 0; bit < (1<<b); ++bit){
            ll idx = 0;
            ll val = (i>>a);
            for(ll j = 0; j < b; ++j){
                if((1<<j)&bit)
                    idx += p3[j]*(val%2);
                else
                    idx += p3[j]*2;
                val /= 2;
            }
            sum[v1-(1<<a)][idx] += s[i]-'0';
        }
    }
    for(ll i = 0; i < q; ++i){
        cin >> s;
        reverse(s.begin(), s.end());
        ll v1 = 0;
        for(ll i = 0; i < s.size(); ++i){
            if(s[i] == '1')
                v1 += p3[i];
            else if(s[i] == '?')
                v1 += 2*p3[i];
        }
        v2 = 0;
        for(ll i = a; i < a+b; ++i){
            if(i >= s.size())
                v2 += 2*p3[i-a];
            else if(s[i] == '1')
                v2 += p3[i-a];
            else if(s[i] == '?')
                v2 += 2*p3[i-a];
        }
        cout << calc(a-1, 1, v1) << '\n';
    }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i = 0; i < s.size(); ++i){
                       ~~^~~~~~~~~~
snake_escaping.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i >= s.size())
                ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -