oj.uz

Submission #396896

# Submission time Handle Problem Language Result Execution time Memory
396896 2021-04-30T23:13:03 Z rqi Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 1333 ms 30304 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

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

const int MOD = 1e9+7;

#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;

// 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 trip[3][1<<20];

void genTrip(){
    for(int i = 0; i < (1<<L); i++){
        trip[2][i] = S[i]-'0';
    }
    for(int typ = 0; typ < 2; typ++){
        array<int, 1<<20> dp;
        array<int, 1<<20> ndp;
        for(int i = 0; i < (1<<20); i++){
            dp[i] = trip[2][i];
            ndp[i] = 0;
        }
        for(int j = 0; j < L; j++){
            for(int i = 0; i < (1<<L); i++){
                if((i>>j)&1){ //put in ?
                    ndp[i] = dp[i-(1<<j)]+dp[i];
                }
                else{
                    if(typ == 1){
                        ndp[i] = dp[i];
                    }
                    else{
                        ndp[i] = dp[i+(1<<j)];    
                    }
                }
            }
            swap(dp, ndp);
            for(int i = 0; i < (1<<L); i++){
                ndp[i] = 0;
            }
        }
        for(int i = 0; i < (1<<L); i++){
            bool is_odd = 0;
            for(int j = 0; j < L; j++){
                if((i>>j)&1){
                    is_odd^=1;
                }
            }
            if(is_odd){
                trip[typ][i] = -dp[i];
            }
            else{
                trip[typ][i] = dp[i];
            }
        }
    }
}

string T;
map<char, int> from_char;

void printTrip(){
    
    
        vi typ_count(3, 0);
        for(auto u: T){
            typ_count[from_char[u]]++;
        }
        int typ = -1;

        int min_typ_count = min(typ_count[0], min(typ_count[1], typ_count[2]));

        for(int i = 0; i < 3; i++){
            if(typ_count[i] == min_typ_count){
                typ = i;
                break;
            }
        }

        // cout << "typ: " << typ << "\n";

        // cout << trip[1][0] << "\n";

        int sub1 = 0; //positions of typ
        int sub2 = 0; //

        if(typ == 2){
            for(int j = 0; j < L; j++){
                int char_type = from_char[T[j]];
                if(char_type == 2){
                    sub1+=(1<<j);
                }
                else if(char_type == 1){
                    sub2+=(1<<j);
                }
            }
        }
        else{
            for(int j = 0; j < L; j++){
                int char_type = from_char[T[j]];
                if(char_type == typ){
                    sub1+=(1<<j);
                }
                else if(char_type == 2){
                    sub2+=(1<<j);
                }
            }
        }
        
        int res = 0;
        for(int i = sub1; ; i = ((i-1)&sub1)){
            res+=trip[typ][i+sub2];
            // if(res >= MOD) res-=MOD;
            // if(res < 0) res+=MOD;
            if(i == 0) break;
        }

        if((typ_count[2]+typ_count[typ])&1){
            res = -res;
            // if(res >= MOD) res-=MOD;
            // if(res < 0) res+=MOD;
        }
        

        cout << res << "\n";
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    from_char['0'] = 0;
    from_char['1'] = 1;
    from_char['?'] = 2;
    cin >> L >> Q;
    cin >> S;

    genTrip();
    for(int i = 1; i <= Q; i++){
        cin >> T;
        reverse(all(T));
        printTrip();
    }

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

    
    
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 32 ms 8556 KB Output is correct
3 Correct 32 ms 8556 KB Output is correct
4 Correct 31 ms 8552 KB Output is correct
5 Correct 31 ms 8540 KB Output is correct
6 Correct 31 ms 8540 KB Output is correct
7 Correct 32 ms 8524 KB Output is correct
8 Correct 36 ms 8500 KB Output is correct
9 Correct 34 ms 8556 KB Output is correct
10 Correct 32 ms 8524 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 32 ms 8556 KB Output is correct
3 Correct 32 ms 8556 KB Output is correct
4 Correct 31 ms 8552 KB Output is correct
5 Correct 31 ms 8540 KB Output is correct
6 Correct 31 ms 8540 KB Output is correct
7 Correct 32 ms 8524 KB Output is correct
8 Correct 36 ms 8500 KB Output is correct
9 Correct 34 ms 8556 KB Output is correct
10 Correct 32 ms 8524 KB Output is correct
11 Correct 456 ms 15364 KB Output is correct
12 Correct 496 ms 15176 KB Output is correct
13 Correct 518 ms 14328 KB Output is correct
14 Correct 527 ms 14344 KB Output is correct
15 Correct 527 ms 15404 KB Output is correct
16 Correct 542 ms 14564 KB Output is correct
17 Correct 546 ms 14532 KB Output is correct
18 Correct 405 ms 16392 KB Output is correct
19 Correct 461 ms 13432 KB Output is correct
20 Correct 498 ms 15108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 32 ms 8556 KB Output is correct
3 Correct 32 ms 8556 KB Output is correct
4 Correct 31 ms 8552 KB Output is correct
5 Correct 31 ms 8540 KB Output is correct
6 Correct 31 ms 8540 KB Output is correct
7 Correct 32 ms 8524 KB Output is correct
8 Correct 36 ms 8500 KB Output is correct
9 Correct 34 ms 8556 KB Output is correct
10 Correct 32 ms 8524 KB Output is correct
11 Correct 456 ms 15364 KB Output is correct
12 Correct 496 ms 15176 KB Output is correct
13 Correct 518 ms 14328 KB Output is correct
14 Correct 527 ms 14344 KB Output is correct
15 Correct 527 ms 15404 KB Output is correct
16 Correct 542 ms 14564 KB Output is correct
17 Correct 546 ms 14532 KB Output is correct
18 Correct 405 ms 16392 KB Output is correct
19 Correct 461 ms 13432 KB Output is correct
20 Correct 498 ms 15108 KB Output is correct
21 Correct 549 ms 15448 KB Output is correct
22 Correct 610 ms 15640 KB Output is correct
23 Correct 612 ms 14632 KB Output is correct
24 Correct 637 ms 14532 KB Output is correct
25 Correct 599 ms 16488 KB Output is correct
26 Correct 656 ms 15072 KB Output is correct
27 Correct 646 ms 15140 KB Output is correct
28 Correct 428 ms 17516 KB Output is correct
29 Correct 568 ms 13544 KB Output is correct
30 Correct 557 ms 15696 KB Output is correct
31 Correct 657 ms 15488 KB Output is correct
32 Correct 646 ms 15496 KB Output is correct
33 Correct 544 ms 14380 KB Output is correct
34 Correct 661 ms 14404 KB Output is correct
35 Correct 653 ms 14764 KB Output is correct
36 Correct 393 ms 13124 KB Output is correct
37 Correct 569 ms 15276 KB Output is correct
38 Correct 567 ms 13380 KB Output is correct
39 Correct 605 ms 14424 KB Output is correct
40 Correct 636 ms 14184 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 32 ms 8556 KB Output is correct
3 Correct 32 ms 8556 KB Output is correct
4 Correct 31 ms 8552 KB Output is correct
5 Correct 31 ms 8540 KB Output is correct
6 Correct 31 ms 8540 KB Output is correct
7 Correct 32 ms 8524 KB Output is correct
8 Correct 36 ms 8500 KB Output is correct
9 Correct 34 ms 8556 KB Output is correct
10 Correct 32 ms 8524 KB Output is correct
11 Correct 210 ms 23256 KB Output is correct
12 Correct 218 ms 23388 KB Output is correct
13 Correct 232 ms 23216 KB Output is correct
14 Correct 282 ms 23252 KB Output is correct
15 Correct 223 ms 23396 KB Output is correct
16 Correct 232 ms 23316 KB Output is correct
17 Correct 268 ms 23116 KB Output is correct
18 Correct 200 ms 23260 KB Output is correct
19 Correct 236 ms 23000 KB Output is correct
20 Correct 214 ms 23128 KB Output is correct
21 Correct 241 ms 23096 KB Output is correct
22 Correct 231 ms 23000 KB Output is correct
23 Correct 213 ms 23016 KB Output is correct
24 Correct 239 ms 23004 KB Output is correct
25 Correct 234 ms 23048 KB Output is correct
26 Correct 196 ms 22864 KB Output is correct
27 Correct 217 ms 23120 KB Output is correct
28 Correct 212 ms 22872 KB Output is correct
29 Correct 222 ms 23020 KB Output is correct
30 Correct 227 ms 23132 KB Output is correct
31 Correct 216 ms 23052 KB Output is correct
32 Correct 246 ms 23060 KB Output is correct
33 Correct 235 ms 23004 KB Output is correct
34 Correct 198 ms 22880 KB Output is correct
35 Correct 254 ms 23000 KB Output is correct
36 Correct 226 ms 23032 KB Output is correct
37 Correct 222 ms 22972 KB Output is correct
38 Correct 225 ms 22976 KB Output is correct
39 Correct 226 ms 23028 KB Output is correct
40 Correct 222 ms 22996 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 32 ms 8556 KB Output is correct
3 Correct 32 ms 8556 KB Output is correct
4 Correct 31 ms 8552 KB Output is correct
5 Correct 31 ms 8540 KB Output is correct
6 Correct 31 ms 8540 KB Output is correct
7 Correct 32 ms 8524 KB Output is correct
8 Correct 36 ms 8500 KB Output is correct
9 Correct 34 ms 8556 KB Output is correct
10 Correct 32 ms 8524 KB Output is correct
11 Correct 456 ms 15364 KB Output is correct
12 Correct 496 ms 15176 KB Output is correct
13 Correct 518 ms 14328 KB Output is correct
14 Correct 527 ms 14344 KB Output is correct
15 Correct 527 ms 15404 KB Output is correct
16 Correct 542 ms 14564 KB Output is correct
17 Correct 546 ms 14532 KB Output is correct
18 Correct 405 ms 16392 KB Output is correct
19 Correct 461 ms 13432 KB Output is correct
20 Correct 498 ms 15108 KB Output is correct
21 Correct 549 ms 15448 KB Output is correct
22 Correct 610 ms 15640 KB Output is correct
23 Correct 612 ms 14632 KB Output is correct
24 Correct 637 ms 14532 KB Output is correct
25 Correct 599 ms 16488 KB Output is correct
26 Correct 656 ms 15072 KB Output is correct
27 Correct 646 ms 15140 KB Output is correct
28 Correct 428 ms 17516 KB Output is correct
29 Correct 568 ms 13544 KB Output is correct
30 Correct 557 ms 15696 KB Output is correct
31 Correct 657 ms 15488 KB Output is correct
32 Correct 646 ms 15496 KB Output is correct
33 Correct 544 ms 14380 KB Output is correct
34 Correct 661 ms 14404 KB Output is correct
35 Correct 653 ms 14764 KB Output is correct
36 Correct 393 ms 13124 KB Output is correct
37 Correct 569 ms 15276 KB Output is correct
38 Correct 567 ms 13380 KB Output is correct
39 Correct 605 ms 14424 KB Output is correct
40 Correct 636 ms 14184 KB Output is correct
41 Correct 210 ms 23256 KB Output is correct
42 Correct 218 ms 23388 KB Output is correct
43 Correct 232 ms 23216 KB Output is correct
44 Correct 282 ms 23252 KB Output is correct
45 Correct 223 ms 23396 KB Output is correct
46 Correct 232 ms 23316 KB Output is correct
47 Correct 268 ms 23116 KB Output is correct
48 Correct 200 ms 23260 KB Output is correct
49 Correct 236 ms 23000 KB Output is correct
50 Correct 214 ms 23128 KB Output is correct
51 Correct 241 ms 23096 KB Output is correct
52 Correct 231 ms 23000 KB Output is correct
53 Correct 213 ms 23016 KB Output is correct
54 Correct 239 ms 23004 KB Output is correct
55 Correct 234 ms 23048 KB Output is correct
56 Correct 196 ms 22864 KB Output is correct
57 Correct 217 ms 23120 KB Output is correct
58 Correct 212 ms 22872 KB Output is correct
59 Correct 222 ms 23020 KB Output is correct
60 Correct 227 ms 23132 KB Output is correct
61 Correct 216 ms 23052 KB Output is correct
62 Correct 246 ms 23060 KB Output is correct
63 Correct 235 ms 23004 KB Output is correct
64 Correct 198 ms 22880 KB Output is correct
65 Correct 254 ms 23000 KB Output is correct
66 Correct 226 ms 23032 KB Output is correct
67 Correct 222 ms 22972 KB Output is correct
68 Correct 225 ms 22976 KB Output is correct
69 Correct 226 ms 23028 KB Output is correct
70 Correct 222 ms 22996 KB Output is correct
71 Correct 890 ms 27708 KB Output is correct
72 Correct 909 ms 27568 KB Output is correct
73 Correct 1035 ms 26080 KB Output is correct
74 Correct 1181 ms 26364 KB Output is correct
75 Correct 950 ms 28456 KB Output is correct
76 Correct 1294 ms 26784 KB Output is correct
77 Correct 1270 ms 26560 KB Output is correct
78 Correct 669 ms 30304 KB Output is correct
79 Correct 920 ms 24448 KB Output is correct
80 Correct 918 ms 27340 KB Output is correct
81 Correct 1105 ms 27260 KB Output is correct
82 Correct 1139 ms 26216 KB Output is correct
83 Correct 856 ms 25340 KB Output is correct
84 Correct 1333 ms 26252 KB Output is correct
85 Correct 1264 ms 26400 KB Output is correct
86 Correct 603 ms 24140 KB Output is correct
87 Correct 900 ms 27092 KB Output is correct
88 Correct 894 ms 24080 KB Output is correct
89 Correct 995 ms 25576 KB Output is correct
90 Correct 1151 ms 26052 KB Output is correct
91 Correct 876 ms 25172 KB Output is correct
92 Correct 1296 ms 26344 KB Output is correct
93 Correct 1251 ms 26144 KB Output is correct
94 Correct 653 ms 24052 KB Output is correct
95 Correct 1119 ms 26228 KB Output is correct
96 Correct 1136 ms 26072 KB Output is correct
97 Correct 1125 ms 26076 KB Output is correct
98 Correct 1119 ms 26004 KB Output is correct
99 Correct 1120 ms 26060 KB Output is correct
100 Correct 1129 ms 26128 KB Output is correct