oj.uz

Submission #991630

# Submission time Handle Problem Language Result Execution time Memory
991630 2024-06-02T17:17:44 Z GrindMachine Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 1811 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 = max(n/2,1);
 
    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 9 ms 59484 KB Output is correct
2 Correct 8 ms 59484 KB Output is correct
3 Correct 8 ms 59540 KB Output is correct
4 Correct 8 ms 59576 KB Output is correct
5 Correct 9 ms 59484 KB Output is correct
6 Correct 9 ms 59484 KB Output is correct
7 Correct 8 ms 59484 KB Output is correct
8 Correct 9 ms 59552 KB Output is correct
9 Correct 8 ms 59560 KB Output is correct
10 Correct 8 ms 59640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59484 KB Output is correct
2 Correct 8 ms 59484 KB Output is correct
3 Correct 8 ms 59540 KB Output is correct
4 Correct 8 ms 59576 KB Output is correct
5 Correct 9 ms 59484 KB Output is correct
6 Correct 9 ms 59484 KB Output is correct
7 Correct 8 ms 59484 KB Output is correct
8 Correct 9 ms 59552 KB Output is correct
9 Correct 8 ms 59560 KB Output is correct
10 Correct 8 ms 59640 KB Output is correct
11 Runtime error 96 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 9 ms 59484 KB Output is correct
2 Correct 8 ms 59484 KB Output is correct
3 Correct 8 ms 59540 KB Output is correct
4 Correct 8 ms 59576 KB Output is correct
5 Correct 9 ms 59484 KB Output is correct
6 Correct 9 ms 59484 KB Output is correct
7 Correct 8 ms 59484 KB Output is correct
8 Correct 9 ms 59552 KB Output is correct
9 Correct 8 ms 59560 KB Output is correct
10 Correct 8 ms 59640 KB Output is correct
11 Runtime error 96 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 9 ms 59484 KB Output is correct
2 Correct 8 ms 59484 KB Output is correct
3 Correct 8 ms 59540 KB Output is correct
4 Correct 8 ms 59576 KB Output is correct
5 Correct 9 ms 59484 KB Output is correct
6 Correct 9 ms 59484 KB Output is correct
7 Correct 8 ms 59484 KB Output is correct
8 Correct 9 ms 59552 KB Output is correct
9 Correct 8 ms 59560 KB Output is correct
10 Correct 8 ms 59640 KB Output is correct
11 Correct 997 ms 61940 KB Output is correct
12 Correct 1006 ms 61704 KB Output is correct
13 Correct 1664 ms 61692 KB Output is correct
14 Correct 1794 ms 61692 KB Output is correct
15 Correct 1346 ms 61940 KB Output is correct
16 Correct 1770 ms 61692 KB Output is correct
17 Correct 1811 ms 61948 KB Output is correct
18 Correct 957 ms 61952 KB Output is correct
19 Correct 978 ms 61696 KB Output is correct
20 Correct 1028 ms 61948 KB Output is correct
21 Correct 1637 ms 61696 KB Output is correct
22 Correct 1728 ms 61696 KB Output is correct
23 Correct 1241 ms 61696 KB Output is correct
24 Correct 1744 ms 61936 KB Output is correct
25 Correct 1800 ms 61692 KB Output is correct
26 Correct 911 ms 61696 KB Output is correct
27 Correct 1004 ms 61716 KB Output is correct
28 Correct 987 ms 61696 KB Output is correct
29 Correct 1540 ms 61708 KB Output is correct
30 Correct 1713 ms 61692 KB Output is correct
31 Correct 1216 ms 61696 KB Output is correct
32 Correct 1764 ms 61696 KB Output is correct
33 Correct 1803 ms 61696 KB Output is correct
34 Correct 1000 ms 61696 KB Output is correct
35 Correct 1677 ms 61948 KB Output is correct
36 Correct 1733 ms 61708 KB Output is correct
37 Correct 1691 ms 61696 KB Output is correct
38 Correct 1677 ms 61696 KB Output is correct
39 Correct 1687 ms 61692 KB Output is correct
40 Correct 1677 ms 61696 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59484 KB Output is correct
2 Correct 8 ms 59484 KB Output is correct
3 Correct 8 ms 59540 KB Output is correct
4 Correct 8 ms 59576 KB Output is correct
5 Correct 9 ms 59484 KB Output is correct
6 Correct 9 ms 59484 KB Output is correct
7 Correct 8 ms 59484 KB Output is correct
8 Correct 9 ms 59552 KB Output is correct
9 Correct 8 ms 59560 KB Output is correct
10 Correct 8 ms 59640 KB Output is correct
11 Runtime error 96 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -