oj.uz

Submission #810207

# Submission time Handle Problem Language Result Execution time Memory
810207 2023-08-06T06:31:41 Z QwertyPi Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 39760 KB 
#include <bits/stdc++.h>
using namespace std;

int a[1 << 20], ans[1 << 20];
int f(char c){
    if(c == '0') return 0;
    if(c == '1') return 1;
    if(c == '?') return 2;
    return -1;
}

vector<pair<long long, int>> Q;
void solve(int L, vector<int> a, int l, int r){
    if(L == 0){
        for(int i = l; i < r; i++){
            ans[Q[i].second] = a[0];
        }
        return;
    }
    int mid_0 = l; while(mid_0 < r && (Q[mid_0].first & (3LL << (L - 1) * 2)) == 0) mid_0++;
    int mid_1 = mid_0; while(mid_1 < r && ((Q[mid_1].first & (3LL << (L - 1) * 2)) >> (L - 1) * 2) == 1) mid_1++;
    vector<int> b(1 << L - 1);
    // 0
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i];
    solve(L - 1, b, l, mid_0);
    // 1
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i + (1 << L - 1)];
    solve(L - 1, b, mid_0, mid_1);
    // ?
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i] + a[i + (1 << L - 1)];
    solve(L - 1, b, mid_1, r);
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int L, q; cin >> L >> q; string s; cin >> s;
    vector<int> a(1 << L); for(int i = 0; i < (1 << L); i++) a[i] = s[i] - '0';
    for(int i = 0; i < q; i++){
        string s; cin >> s; reverse(s.begin(), s.end());
        long long b = 0;
        for(int j = 0; j < L; j++){
            b |= f(s[j]) * (1LL << j * 2);
        }
        Q.push_back({b, i});
    }
    sort(Q.begin(), Q.end());
    solve(L, a, 0, Q.size());

    for(int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

Compilation message

snake_escaping.cpp: In function 'void solve(int, std::vector<int>, int, int)':
snake_escaping.cpp:22:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   22 |     vector<int> b(1 << L - 1);
      |                        ~~^~~
snake_escaping.cpp:24:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i];
      |                              ~~^~~
snake_escaping.cpp:27:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:27:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i + (1 << L - 1)];
      |                                                              ~~^~~
snake_escaping.cpp:30:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i] + a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:30:71: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i] + a[i + (1 << L - 1)];
      |                                                                     ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 279 ms 34792 KB Output is correct
12 Correct 302 ms 34396 KB Output is correct
13 Correct 295 ms 33628 KB Output is correct
14 Correct 312 ms 33828 KB Output is correct
15 Correct 285 ms 34808 KB Output is correct
16 Correct 296 ms 33876 KB Output is correct
17 Correct 302 ms 33908 KB Output is correct
18 Correct 157 ms 35744 KB Output is correct
19 Correct 290 ms 32808 KB Output is correct
20 Correct 276 ms 34400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 279 ms 34792 KB Output is correct
12 Correct 302 ms 34396 KB Output is correct
13 Correct 295 ms 33628 KB Output is correct
14 Correct 312 ms 33828 KB Output is correct
15 Correct 285 ms 34808 KB Output is correct
16 Correct 296 ms 33876 KB Output is correct
17 Correct 302 ms 33908 KB Output is correct
18 Correct 157 ms 35744 KB Output is correct
19 Correct 290 ms 32808 KB Output is correct
20 Correct 276 ms 34400 KB Output is correct
21 Correct 357 ms 37748 KB Output is correct
22 Correct 387 ms 37852 KB Output is correct
23 Correct 367 ms 36908 KB Output is correct
24 Correct 407 ms 36724 KB Output is correct
25 Correct 346 ms 38744 KB Output is correct
26 Correct 384 ms 37336 KB Output is correct
27 Correct 402 ms 37200 KB Output is correct
28 Correct 225 ms 39760 KB Output is correct
29 Correct 341 ms 35724 KB Output is correct
30 Correct 374 ms 37948 KB Output is correct
31 Correct 368 ms 37788 KB Output is correct
32 Correct 362 ms 37728 KB Output is correct
33 Correct 341 ms 36644 KB Output is correct
34 Correct 416 ms 36768 KB Output is correct
35 Correct 389 ms 37320 KB Output is correct
36 Correct 229 ms 35788 KB Output is correct
37 Correct 356 ms 37796 KB Output is correct
38 Correct 371 ms 35700 KB Output is correct
39 Correct 364 ms 36896 KB Output is correct
40 Correct 356 ms 36728 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Execution timed out 2076 ms 20588 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 279 ms 34792 KB Output is correct
12 Correct 302 ms 34396 KB Output is correct
13 Correct 295 ms 33628 KB Output is correct
14 Correct 312 ms 33828 KB Output is correct
15 Correct 285 ms 34808 KB Output is correct
16 Correct 296 ms 33876 KB Output is correct
17 Correct 302 ms 33908 KB Output is correct
18 Correct 157 ms 35744 KB Output is correct
19 Correct 290 ms 32808 KB Output is correct
20 Correct 276 ms 34400 KB Output is correct
21 Correct 357 ms 37748 KB Output is correct
22 Correct 387 ms 37852 KB Output is correct
23 Correct 367 ms 36908 KB Output is correct
24 Correct 407 ms 36724 KB Output is correct
25 Correct 346 ms 38744 KB Output is correct
26 Correct 384 ms 37336 KB Output is correct
27 Correct 402 ms 37200 KB Output is correct
28 Correct 225 ms 39760 KB Output is correct
29 Correct 341 ms 35724 KB Output is correct
30 Correct 374 ms 37948 KB Output is correct
31 Correct 368 ms 37788 KB Output is correct
32 Correct 362 ms 37728 KB Output is correct
33 Correct 341 ms 36644 KB Output is correct
34 Correct 416 ms 36768 KB Output is correct
35 Correct 389 ms 37320 KB Output is correct
36 Correct 229 ms 35788 KB Output is correct
37 Correct 356 ms 37796 KB Output is correct
38 Correct 371 ms 35700 KB Output is correct
39 Correct 364 ms 36896 KB Output is correct
40 Correct 356 ms 36728 KB Output is correct
41 Execution timed out 2076 ms 20588 KB Time limit exceeded
42 Halted 0 ms 0 KB -