oj.uz

Submission #697658

# Submission time Handle Problem Language Result Execution time Memory
697658 2023-02-10T16:29:58 Z Jarif_Rahman Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 65536 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int p3[16] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907};
int v[1<<20];
vector<pair<int, int>> queries[1<<10];
//int dp[1594323];
int dp[59049];

void bruteforce(str &s, int &x, int &i, int k = 0, int index = 0){
    if(k == 10){
        queries[index].pb({x, i});
        return;
    }
    if(s[10+k] != '1') bruteforce(s, x, i, k+1, index);
    if(s[10+k] != '0') bruteforce(s, x, i, k+1, index+(1<<k));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int L, Q; cin >> L >> Q;
    for(int i = 0; i < (1<<L); i++){
        char c; cin >> c;
        v[i] = c-'0';
    }

    vector<int> ans(Q, 0);
    for(int i = 0; i < Q; i++){
        str s; cin >> s;
        if(L < 20) s = str(20-L, '0')+s;
        reverse(s.begin(), s.end());
        int x = 0;
        for(int j = 0; j < 10; j++){
            if(s[j] == '?') x+=p3[j]*2;
            else x+=(s[j]-'0')*p3[j];
        }

        bruteforce(s, x, i);
    }

    for(int k = 0; k < (1<<10); k++){
        if(queries[k].empty()) continue;
        fill(dp, dp+p3[10], 0);
        for(int i = k*(1<<10); i < (k+1)*(1<<10); i++){
            int x = 0;
            for(int j = 0; j < 10; j++) if(i&(1<<j)) x+=p3[j];
            dp[x]+=v[i];
        }

        for(int j = 0; j < 10; j++) for(int i = 0; i < p3[10]; i++){
            if((i/p3[j])%3 == 2){
                dp[i]+=dp[i-p3[j]*2]+dp[i-p3[j]];
            }
        }

        for(auto [x, i]: queries[k]) ans[i]+=dp[x];
    }

    for(int x: ans) cout << x << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 612 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 624 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 4 ms 628 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 624 KB Output is correct
10 Correct 4 ms 596 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 612 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 624 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 4 ms 628 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 624 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 314 ms 16748 KB Output is correct
12 Correct 307 ms 16536 KB Output is correct
13 Correct 292 ms 15796 KB Output is correct
14 Correct 323 ms 15856 KB Output is correct
15 Correct 383 ms 16792 KB Output is correct
16 Correct 298 ms 16004 KB Output is correct
17 Correct 291 ms 15984 KB Output is correct
18 Correct 265 ms 17960 KB Output is correct
19 Correct 273 ms 14804 KB Output is correct
20 Correct 307 ms 16460 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 612 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 624 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 4 ms 628 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 624 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 314 ms 16748 KB Output is correct
12 Correct 307 ms 16536 KB Output is correct
13 Correct 292 ms 15796 KB Output is correct
14 Correct 323 ms 15856 KB Output is correct
15 Correct 383 ms 16792 KB Output is correct
16 Correct 298 ms 16004 KB Output is correct
17 Correct 291 ms 15984 KB Output is correct
18 Correct 265 ms 17960 KB Output is correct
19 Correct 273 ms 14804 KB Output is correct
20 Correct 307 ms 16460 KB Output is correct
21 Correct 477 ms 42972 KB Output is correct
22 Correct 472 ms 41332 KB Output is correct
23 Correct 391 ms 24680 KB Output is correct
24 Correct 400 ms 24892 KB Output is correct
25 Correct 501 ms 42156 KB Output is correct
26 Correct 423 ms 27656 KB Output is correct
27 Correct 418 ms 27160 KB Output is correct
28 Runtime error 520 ms 65536 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 612 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 624 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 4 ms 628 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 624 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Execution timed out 2088 ms 29360 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 612 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 624 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 4 ms 628 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 624 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 314 ms 16748 KB Output is correct
12 Correct 307 ms 16536 KB Output is correct
13 Correct 292 ms 15796 KB Output is correct
14 Correct 323 ms 15856 KB Output is correct
15 Correct 383 ms 16792 KB Output is correct
16 Correct 298 ms 16004 KB Output is correct
17 Correct 291 ms 15984 KB Output is correct
18 Correct 265 ms 17960 KB Output is correct
19 Correct 273 ms 14804 KB Output is correct
20 Correct 307 ms 16460 KB Output is correct
21 Correct 477 ms 42972 KB Output is correct
22 Correct 472 ms 41332 KB Output is correct
23 Correct 391 ms 24680 KB Output is correct
24 Correct 400 ms 24892 KB Output is correct
25 Correct 501 ms 42156 KB Output is correct
26 Correct 423 ms 27656 KB Output is correct
27 Correct 418 ms 27160 KB Output is correct
28 Runtime error 520 ms 65536 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -