oj.uz

Submission #1023351

# Submission time Handle Problem Language Result Execution time Memory
1023351 2024-07-14T16:41:14 Z snpmrnhlol Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 19216 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int cost[1<<N],cost0[1<<N],cost1[1<<N];
vector <int> pos;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i = 0;i < (1<<n);i++){
        char ch;
        cin>>ch;
        ch-='0';
        cost[i]+=ch;
        cost0[i]+=ch;
        cost1[i]+=ch;
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < (1<<i);j++){
            for(int k = 0;k < (1<<n);k+=(1<<(i + 1))){
                cost0[(1<<i) + j + k]+=cost0[j + k];
                ///0 - 0
                ///1 - 0 and 1
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < (1<<i);j++){
            for(int k = 0;k < (1<<n);k+=(1<<(i + 1))){
                cost1[j + k]+=cost1[j + k + (1<<i)];
                ///0 - 0 and 1
                ///1 - 1
            }
        }
    }
    for(int i = 0;i < q;i++){
        int cnt[3];
        cnt[0] = cnt[1] = cnt[2] = 0;
        string x;
        cin>>x;
        for(int j = 0;j < x.size();j++){
            if(x[j] == '0'){
                cnt[0]++;
            }else if(x[j] == '1'){
                cnt[1]++;
            }else{
                cnt[2]++;
            }
        }
        pos.clear();
        if(0){
            ///0 count low
            ///use cost1
            for(int k = 0;k < n;k++){
                if(x[k] == '0'){
                    pos.push_back(n - k - 1);
                }
            }
            int nr = 0;
            for(int k = 0;k < n;k++){
                if(x[k] == '1'){
                    nr = nr*2 + 1;
                }else{
                    nr = nr*2;
                }
            }
            int ans = 0;
            for(int k = 0;k < (1<<pos.size());k++){
                if(k%2 == 0)ans+=cost1[nr];
                else ans-=cost1[nr];
                if(k != (1<<pos.size()) - 1)nr^=(1<<pos[__builtin_ctz(k + 1)]);
            }
            cout<<ans<<'\n';
        }else if(0){
            ///1 count low
            ///use cost0
            for(int k = 0;k < n;k++){
                if(x[k] == '?'){
                    pos.push_back(n - k - 1);
                }
            }
            int nr = 0;
            for(int k = 0;k < n;k++){
                if(x[k] == '0'){
                    nr = nr*2;
                }else{
                    nr = nr*2 + 1;
                }
            }
            int ans = 0;
            for(int k = 0;k < (1<<pos.size());k++){
                if(k%2 == 0)ans+=cost0[nr];
                else ans-=cost0[nr];
                if(k != (1<<pos.size()) - 1)nr^=(1<<pos[__builtin_ctz(k + 1)]);
            }
            cout<<ans<<'\n';
        }else{
            ///? count low
            ///use cost
            for(int k = 0;k < n;k++){
                if(x[k] == '?'){
                    pos.push_back(n - k - 1);
                }
            }
            int nr = 0;
            for(int k = 0;k < n;k++){
                if(x[k] == '1'){
                    nr = nr*2 + 1;
                }else{
                    nr = nr*2;
                }
            }
            int ans = 0;
            for(int k = 0;k < (1<<pos.size());k++){
                ans+=cost[nr];
                //cout<<nr<<' '<<(1<<__builtin_ctz(k + 1))<<'\n';
                if(k != (1<<pos.size()) - 1)nr^=(1<<pos[__builtin_ctz(k + 1)]);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j = 0;j < x.size();j++){
      |                       ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 179 ms 15236 KB Output is correct
12 Correct 203 ms 14760 KB Output is correct
13 Correct 137 ms 13968 KB Output is correct
14 Correct 130 ms 14252 KB Output is correct
15 Correct 222 ms 15184 KB Output is correct
16 Correct 158 ms 14420 KB Output is correct
17 Correct 176 ms 14148 KB Output is correct
18 Correct 1143 ms 16216 KB Output is correct
19 Correct 107 ms 13028 KB Output is correct
20 Correct 240 ms 14840 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 179 ms 15236 KB Output is correct
12 Correct 203 ms 14760 KB Output is correct
13 Correct 137 ms 13968 KB Output is correct
14 Correct 130 ms 14252 KB Output is correct
15 Correct 222 ms 15184 KB Output is correct
16 Correct 158 ms 14420 KB Output is correct
17 Correct 176 ms 14148 KB Output is correct
18 Correct 1143 ms 16216 KB Output is correct
19 Correct 107 ms 13028 KB Output is correct
20 Correct 240 ms 14840 KB Output is correct
21 Correct 313 ms 18092 KB Output is correct
22 Correct 404 ms 18272 KB Output is correct
23 Correct 202 ms 17420 KB Output is correct
24 Correct 161 ms 17232 KB Output is correct
25 Correct 442 ms 19216 KB Output is correct
26 Correct 239 ms 17744 KB Output is correct
27 Correct 218 ms 17488 KB Output is correct
28 Execution timed out 2059 ms 5456 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 327 ms 15040 KB Output is correct
12 Correct 601 ms 15016 KB Output is correct
13 Correct 196 ms 14932 KB Output is correct
14 Correct 205 ms 14932 KB Output is correct
15 Correct 1227 ms 15188 KB Output is correct
16 Correct 225 ms 14928 KB Output is correct
17 Correct 219 ms 14788 KB Output is correct
18 Execution timed out 2060 ms 13916 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 179 ms 15236 KB Output is correct
12 Correct 203 ms 14760 KB Output is correct
13 Correct 137 ms 13968 KB Output is correct
14 Correct 130 ms 14252 KB Output is correct
15 Correct 222 ms 15184 KB Output is correct
16 Correct 158 ms 14420 KB Output is correct
17 Correct 176 ms 14148 KB Output is correct
18 Correct 1143 ms 16216 KB Output is correct
19 Correct 107 ms 13028 KB Output is correct
20 Correct 240 ms 14840 KB Output is correct
21 Correct 313 ms 18092 KB Output is correct
22 Correct 404 ms 18272 KB Output is correct
23 Correct 202 ms 17420 KB Output is correct
24 Correct 161 ms 17232 KB Output is correct
25 Correct 442 ms 19216 KB Output is correct
26 Correct 239 ms 17744 KB Output is correct
27 Correct 218 ms 17488 KB Output is correct
28 Execution timed out 2059 ms 5456 KB Time limit exceeded
29 Halted 0 ms 0 KB -