oj.uz

Submission #991626

# Submission time Handle Problem Language Result Execution time Memory
991626 2024-06-02T17:13:02 Z GrindMachine Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 1830 ms 65536 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

int8_t ok_mem[59049][1024];

void solve(int test_case)
{
    int n,q; cin >> n >> q;
    string s; cin >> s;
    int B = min(n,10);

    vector<int> pow3(n+5);
    pow3[0] = 1;
    rep1(i,n) pow3[i] = pow3[i-1]*3;

    vector<pii> queries(q);
    rep(id,q){
        string t; cin >> t;
        int first_t = 0, last_t = 0;
        rep(i,sz(t)){
            ll x = 0;
            if(t[i] == '0') x = 0;
            if(t[i] == '1') x = 1;
            if(t[i] == '?') x = 2;
            if(i < B) first_t = first_t*3+x;
            else last_t = last_t*3+x;
        }

        queries[id] = {first_t,last_t};
    }

    vector<int> get_mask_mem(1<<(n-B),-2);

    auto get_mask = [&](ll x){
        if(get_mask_mem[x] != -2) return get_mask_mem[x];

        int mask = 0;
        rep(bit,n-B){
            int b = 0;
            if(x&(1<<bit)) b = 1;
            mask += pow3[bit]*b;
        }

        return get_mask_mem[x] = mask;
    };

    vector<int> get_lsq_mem(pow3[n-B],-2);

    auto get_lsq = [&](ll x){
        if(get_lsq_mem[x] != -2) return get_lsq_mem[x];

        int ox = x;
        int pos = 0;
        while(x){
            int b = x%3;
            x /= 3;
            if(b == 2) return get_lsq_mem[ox] = pos;
            pos++; 
        }
    
        return get_lsq_mem[ox] = -1;        
    };

    memset(ok_mem,-1,sizeof ok_mem);

    auto ok = [&](int mask1, int mask2){
        if(ok_mem[mask1][mask2] != -1) return ok_mem[mask1][mask2];
        auto omask1 = mask1, omask2 = mask2;

        rev(b,B-1,0){
            int b1 = 0, b2 = 0;
            b1 = mask1%3;
            mask1 /= 3;
            if(mask2&(1<<(B-b-1))) b2 = 1;

            if(b1 == 2 or b1 == b2){

            }
            else{
                return ok_mem[omask1][omask2] = false;
            }
        }

        return ok_mem[omask1][omask2] = true;
    };

    vector<int> ans(q);
    vector<int> dp(pow3[n-B]);

    rep(mask1,1<<B){
        fill(all(dp),0);

        rep(i,1<<n){
            int firstB = i>>(n-B);
            int lastB = i^(firstB<<(n-B));
            if(firstB != mask1) conts;
            dp[get_mask(lastB)] += s[i]-'0';
        }

        rep(mask2,pow3[n-B]){
            int lsq = get_lsq(mask2);
            if(lsq == -1) conts;
            rep(x,2){
                int mask3 = mask2-pow3[lsq]*2+pow3[lsq]*x;
                dp[mask2] += dp[mask3];
            }
        }

        rep(id,q){
            if(ok(queries[id].ff,mask1)){
                ans[id] += dp[queries[id].ss];
            }
        }
    }

    rep(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 59480 KB Output is correct
2 Correct 21 ms 59484 KB Output is correct
3 Correct 23 ms 59484 KB Output is correct
4 Correct 23 ms 59484 KB Output is correct
5 Correct 26 ms 59484 KB Output is correct
6 Correct 25 ms 59524 KB Output is correct
7 Correct 25 ms 59484 KB Output is correct
8 Correct 14 ms 59628 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 20 ms 59484 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 59480 KB Output is correct
2 Correct 21 ms 59484 KB Output is correct
3 Correct 23 ms 59484 KB Output is correct
4 Correct 23 ms 59484 KB Output is correct
5 Correct 26 ms 59484 KB Output is correct
6 Correct 25 ms 59524 KB Output is correct
7 Correct 25 ms 59484 KB Output is correct
8 Correct 14 ms 59628 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 20 ms 59484 KB Output is correct
11 Runtime error 97 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 59480 KB Output is correct
2 Correct 21 ms 59484 KB Output is correct
3 Correct 23 ms 59484 KB Output is correct
4 Correct 23 ms 59484 KB Output is correct
5 Correct 26 ms 59484 KB Output is correct
6 Correct 25 ms 59524 KB Output is correct
7 Correct 25 ms 59484 KB Output is correct
8 Correct 14 ms 59628 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 20 ms 59484 KB Output is correct
11 Runtime error 97 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 59480 KB Output is correct
2 Correct 21 ms 59484 KB Output is correct
3 Correct 23 ms 59484 KB Output is correct
4 Correct 23 ms 59484 KB Output is correct
5 Correct 26 ms 59484 KB Output is correct
6 Correct 25 ms 59524 KB Output is correct
7 Correct 25 ms 59484 KB Output is correct
8 Correct 14 ms 59628 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 20 ms 59484 KB Output is correct
11 Correct 979 ms 61940 KB Output is correct
12 Correct 985 ms 63948 KB Output is correct
13 Correct 1533 ms 63740 KB Output is correct
14 Correct 1729 ms 63744 KB Output is correct
15 Correct 1309 ms 64012 KB Output is correct
16 Correct 1830 ms 63752 KB Output is correct
17 Correct 1807 ms 63760 KB Output is correct
18 Correct 920 ms 64012 KB Output is correct
19 Correct 949 ms 63736 KB Output is correct
20 Correct 963 ms 64012 KB Output is correct
21 Correct 1601 ms 63768 KB Output is correct
22 Correct 1758 ms 63756 KB Output is correct
23 Correct 1186 ms 63736 KB Output is correct
24 Correct 1720 ms 63748 KB Output is correct
25 Correct 1795 ms 63744 KB Output is correct
26 Correct 894 ms 63984 KB Output is correct
27 Correct 1035 ms 63988 KB Output is correct
28 Correct 981 ms 63736 KB Output is correct
29 Correct 1573 ms 63748 KB Output is correct
30 Correct 1796 ms 63752 KB Output is correct
31 Correct 1244 ms 63752 KB Output is correct
32 Correct 1786 ms 63760 KB Output is correct
33 Correct 1797 ms 63752 KB Output is correct
34 Correct 906 ms 63756 KB Output is correct
35 Correct 1705 ms 63756 KB Output is correct
36 Correct 1708 ms 63760 KB Output is correct
37 Correct 1699 ms 63736 KB Output is correct
38 Correct 1696 ms 63776 KB Output is correct
39 Correct 1676 ms 63744 KB Output is correct
40 Correct 1691 ms 63756 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 59480 KB Output is correct
2 Correct 21 ms 59484 KB Output is correct
3 Correct 23 ms 59484 KB Output is correct
4 Correct 23 ms 59484 KB Output is correct
5 Correct 26 ms 59484 KB Output is correct
6 Correct 25 ms 59524 KB Output is correct
7 Correct 25 ms 59484 KB Output is correct
8 Correct 14 ms 59628 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 20 ms 59484 KB Output is correct
11 Runtime error 97 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -