oj.uz

Submission #964573

# Submission time Handle Problem Language Result Execution time Memory
964573 2024-04-17T06:44:12 Z onebit1024 Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 15420 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

const double PI=3.141592653589;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif


int n,q;
vector<int>pref;
int solve(int l, int r, const string &s, int k){
    int m = (l+r)/2;
    if(s[k]=='0')r = m;
    else if(s[k]=='1')l = m+1;
    if(k==0)return pref[r]  - (l==0?0:pref[l-1]);

    if(s[k]!='?')return solve(l,r,s,k-1);
    else return solve(l,m,s,k-1) + solve(m+1, r, s,k-1);
}
void solve()
{
    cin >> n >> q;
    int t = (1ll<<n);
    string s;cin >> s;
    pref = vector<int>(t+1);
    pref[0] = s[0]-'0';
    for(int i = 1;i<t;++i)pref[i] = pref[i-1] + (s[i]-'0');
    while(q--){
        string s;cin >> s;
        reverse(all(s));
        cout << solve(0,t-1,s,n-1) << endl;
    }
}   

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    

    int T=1;
    for(int i = 1;i<=T;++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 417 ms 15052 KB Output is correct
12 Correct 556 ms 14880 KB Output is correct
13 Correct 315 ms 13904 KB Output is correct
14 Correct 345 ms 14140 KB Output is correct
15 Correct 731 ms 15420 KB Output is correct
16 Correct 439 ms 14320 KB Output is correct
17 Correct 413 ms 14228 KB Output is correct
18 Execution timed out 2025 ms 13368 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 417 ms 15052 KB Output is correct
12 Correct 556 ms 14880 KB Output is correct
13 Correct 315 ms 13904 KB Output is correct
14 Correct 345 ms 14140 KB Output is correct
15 Correct 731 ms 15420 KB Output is correct
16 Correct 439 ms 14320 KB Output is correct
17 Correct 413 ms 14228 KB Output is correct
18 Execution timed out 2025 ms 13368 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 376 ms 11992 KB Output is correct
12 Correct 829 ms 11920 KB Output is correct
13 Correct 68 ms 12020 KB Output is correct
14 Correct 130 ms 12056 KB Output is correct
15 Execution timed out 2047 ms 12000 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 417 ms 15052 KB Output is correct
12 Correct 556 ms 14880 KB Output is correct
13 Correct 315 ms 13904 KB Output is correct
14 Correct 345 ms 14140 KB Output is correct
15 Correct 731 ms 15420 KB Output is correct
16 Correct 439 ms 14320 KB Output is correct
17 Correct 413 ms 14228 KB Output is correct
18 Execution timed out 2025 ms 13368 KB Time limit exceeded
19 Halted 0 ms 0 KB -