oj.uz

Submission #396724

# Submission time Handle Problem Language Result Execution time Memory
396724 2021-04-30T16:23:09 Z rqi Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 413 ms 57572 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mx = 1000005;
int L, Q;
string S;
string T[mx];

int three_pow[15];
int three_sub[1594323];

void smallL(){
    three_pow[0] = 1;
    for(int i = 1; i <= L; i++){
        three_pow[i] = three_pow[i-1]*3;
    }
    for(int i = 0; i < three_pow[L]; i++){
        int sub = i;
        int sum = 0;
        for(int j = 0; j < L; j++){
            if(sub % 3 == 2){
                //cout << i << " " << i-2*three_pow[j] << " " << i-1*three_pow[j] << "\n";
                three_sub[i] = three_sub[i-2*three_pow[j]]+three_sub[i-1*three_pow[j]];
                sum = -1;
                break;
            }
            if(sub % 3 == 1){
                sum+=(1<<j);
            }
            sub/=3;
        }
        if(sum != -1){
            three_sub[i] = S[sum]-'0';
            //cout << i << " " << three_sub[i] << "\n";
        }
    }

    //cout << "three_sub[2]: " << three_sub[8] << "\n";

    for(int i = 1; i <= Q; i++){
        int sub = 0;
        for(int j = 0; j < L; j++){
            if(T[i][j] == '1'){
                sub+=three_pow[j];
            }
            else if(T[i][j] == '?'){
                sub+=2*three_pow[j];
            }
        }
        cout << three_sub[sub] << "\n";
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> L >> Q;
    cin >> S;
    for(int i = 1; i <= Q; i++){
        cin >> T[i];
        reverse(all(T[i]));
    }

    if(L <= 13){
        smallL();
        exit(0);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31780 KB Output is correct
2 Correct 21 ms 31880 KB Output is correct
3 Correct 20 ms 31816 KB Output is correct
4 Correct 20 ms 31820 KB Output is correct
5 Correct 19 ms 31872 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct
7 Correct 21 ms 31820 KB Output is correct
8 Correct 20 ms 31804 KB Output is correct
9 Correct 21 ms 31888 KB Output is correct
10 Correct 20 ms 31832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31780 KB Output is correct
2 Correct 21 ms 31880 KB Output is correct
3 Correct 20 ms 31816 KB Output is correct
4 Correct 20 ms 31820 KB Output is correct
5 Correct 19 ms 31872 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct
7 Correct 21 ms 31820 KB Output is correct
8 Correct 20 ms 31804 KB Output is correct
9 Correct 21 ms 31888 KB Output is correct
10 Correct 20 ms 31832 KB Output is correct
11 Correct 255 ms 46700 KB Output is correct
12 Correct 274 ms 46216 KB Output is correct
13 Correct 301 ms 45508 KB Output is correct
14 Correct 301 ms 45580 KB Output is correct
15 Correct 270 ms 46632 KB Output is correct
16 Correct 290 ms 45808 KB Output is correct
17 Correct 300 ms 45764 KB Output is correct
18 Correct 219 ms 47732 KB Output is correct
19 Correct 254 ms 44612 KB Output is correct
20 Correct 266 ms 46352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31780 KB Output is correct
2 Correct 21 ms 31880 KB Output is correct
3 Correct 20 ms 31816 KB Output is correct
4 Correct 20 ms 31820 KB Output is correct
5 Correct 19 ms 31872 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct
7 Correct 21 ms 31820 KB Output is correct
8 Correct 20 ms 31804 KB Output is correct
9 Correct 21 ms 31888 KB Output is correct
10 Correct 20 ms 31832 KB Output is correct
11 Correct 255 ms 46700 KB Output is correct
12 Correct 274 ms 46216 KB Output is correct
13 Correct 301 ms 45508 KB Output is correct
14 Correct 301 ms 45580 KB Output is correct
15 Correct 270 ms 46632 KB Output is correct
16 Correct 290 ms 45808 KB Output is correct
17 Correct 300 ms 45764 KB Output is correct
18 Correct 219 ms 47732 KB Output is correct
19 Correct 254 ms 44612 KB Output is correct
20 Correct 266 ms 46352 KB Output is correct
21 Correct 295 ms 55536 KB Output is correct
22 Correct 322 ms 55712 KB Output is correct
23 Correct 366 ms 54684 KB Output is correct
24 Correct 341 ms 54596 KB Output is correct
25 Correct 316 ms 56608 KB Output is correct
26 Correct 384 ms 55104 KB Output is correct
27 Correct 411 ms 55024 KB Output is correct
28 Correct 242 ms 57572 KB Output is correct
29 Correct 286 ms 53528 KB Output is correct
30 Correct 309 ms 55748 KB Output is correct
31 Correct 338 ms 55568 KB Output is correct
32 Correct 379 ms 55496 KB Output is correct
33 Correct 336 ms 54456 KB Output is correct
34 Correct 357 ms 54596 KB Output is correct
35 Correct 413 ms 55064 KB Output is correct
36 Correct 229 ms 53572 KB Output is correct
37 Correct 305 ms 55524 KB Output is correct
38 Correct 321 ms 53540 KB Output is correct
39 Correct 368 ms 54800 KB Output is correct
40 Correct 361 ms 54552 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31780 KB Output is correct
2 Correct 21 ms 31880 KB Output is correct
3 Correct 20 ms 31816 KB Output is correct
4 Correct 20 ms 31820 KB Output is correct
5 Correct 19 ms 31872 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct
7 Correct 21 ms 31820 KB Output is correct
8 Correct 20 ms 31804 KB Output is correct
9 Correct 21 ms 31888 KB Output is correct
10 Correct 20 ms 31832 KB Output is correct
11 Incorrect 32 ms 36968 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31780 KB Output is correct
2 Correct 21 ms 31880 KB Output is correct
3 Correct 20 ms 31816 KB Output is correct
4 Correct 20 ms 31820 KB Output is correct
5 Correct 19 ms 31872 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct
7 Correct 21 ms 31820 KB Output is correct
8 Correct 20 ms 31804 KB Output is correct
9 Correct 21 ms 31888 KB Output is correct
10 Correct 20 ms 31832 KB Output is correct
11 Correct 255 ms 46700 KB Output is correct
12 Correct 274 ms 46216 KB Output is correct
13 Correct 301 ms 45508 KB Output is correct
14 Correct 301 ms 45580 KB Output is correct
15 Correct 270 ms 46632 KB Output is correct
16 Correct 290 ms 45808 KB Output is correct
17 Correct 300 ms 45764 KB Output is correct
18 Correct 219 ms 47732 KB Output is correct
19 Correct 254 ms 44612 KB Output is correct
20 Correct 266 ms 46352 KB Output is correct
21 Correct 295 ms 55536 KB Output is correct
22 Correct 322 ms 55712 KB Output is correct
23 Correct 366 ms 54684 KB Output is correct
24 Correct 341 ms 54596 KB Output is correct
25 Correct 316 ms 56608 KB Output is correct
26 Correct 384 ms 55104 KB Output is correct
27 Correct 411 ms 55024 KB Output is correct
28 Correct 242 ms 57572 KB Output is correct
29 Correct 286 ms 53528 KB Output is correct
30 Correct 309 ms 55748 KB Output is correct
31 Correct 338 ms 55568 KB Output is correct
32 Correct 379 ms 55496 KB Output is correct
33 Correct 336 ms 54456 KB Output is correct
34 Correct 357 ms 54596 KB Output is correct
35 Correct 413 ms 55064 KB Output is correct
36 Correct 229 ms 53572 KB Output is correct
37 Correct 305 ms 55524 KB Output is correct
38 Correct 321 ms 53540 KB Output is correct
39 Correct 368 ms 54800 KB Output is correct
40 Correct 361 ms 54552 KB Output is correct
41 Incorrect 32 ms 36968 KB Output isn't correct
42 Halted 0 ms 0 KB -