oj.uz

Submission #1033218

# Submission time Handle Problem Language Result Execution time Memory
1033218 2024-07-24T14:25:09 Z Andrey Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 27220 KB 
#include<bits/stdc++.h>
using namespace std;
 
int dp[(1 << 20)][20][2];
int br[(1 << 20)][2];

void sos(int x) {
    for(int i = 0; i < (1 << 20); i++) {
        dp[i][0][x] = br[i][x];
        if(i%2) {
            dp[i][0][x]+=br[i-1][x];
        }
        for(int j = 1; j < 20; j++) {
            dp[i][j][x] = dp[i][j-1][x];
            if(i&(1 << j)) {
                dp[i][j][x]+=dp[i-(1 << j)][j-1][x];
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int l,q;
    cin >> l >> q;
    for(int i = 0; i < (1 << 20); i++) {
        br[i][0] = 0;
        br[i][1] = 0;
    }
    for(int i = 0; i < (1 << l); i++) {
        char a;
        cin >> a;
        br[i][0] = a-'0';
        br[(1 << 20)-1-i][1] = a-'0';
    }
    //sos(0);
    //sos(1);
    for(int i = 0; i < q; i++) {
        vector<int> wow(20);
        int br0 = 20-l,br1 = 0,br2 = 0,ans = 0;
        for(int j = l-1; j >= 0; j--) {
            char a;
            cin >> a;
            if(a == '?') {
                wow[j] = 2;
            }
            else {
                wow[j] = a-'0';
            }
            if(wow[j] == 0) {
                br0++;
            }
            else if(wow[j] == 1) {
                br1++;
            }
            else {
                br2++;
            }
        }
        if(true) {
            int x = 0,y = 0,c;
            for(int j = 0; j < 20; j++) {
                if(wow[j] == 1) {
                    x+=(1 << j);
                }
                if(wow[j] == 2) {
                    y+=(1 << j);
                }
            }
            c = y;
            while(true) {
               // cout << x << " " << c << endl;
                ans+=br[x+c][0];
                if(c == 0) {
                    break;
                }
                c = (c-1)&y;
            }
            cout << ans << "\n";
        }
        
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 3 ms 8644 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 5 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 3 ms 8644 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 5 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 198 ms 23384 KB Output is correct
12 Correct 207 ms 22868 KB Output is correct
13 Correct 194 ms 22340 KB Output is correct
14 Correct 178 ms 22356 KB Output is correct
15 Correct 255 ms 23376 KB Output is correct
16 Correct 201 ms 22608 KB Output is correct
17 Correct 200 ms 22352 KB Output is correct
18 Correct 918 ms 24280 KB Output is correct
19 Correct 197 ms 21508 KB Output is correct
20 Correct 242 ms 22920 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 3 ms 8644 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 5 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 198 ms 23384 KB Output is correct
12 Correct 207 ms 22868 KB Output is correct
13 Correct 194 ms 22340 KB Output is correct
14 Correct 178 ms 22356 KB Output is correct
15 Correct 255 ms 23376 KB Output is correct
16 Correct 201 ms 22608 KB Output is correct
17 Correct 200 ms 22352 KB Output is correct
18 Correct 918 ms 24280 KB Output is correct
19 Correct 197 ms 21508 KB Output is correct
20 Correct 242 ms 22920 KB Output is correct
21 Correct 343 ms 26196 KB Output is correct
22 Correct 338 ms 26448 KB Output is correct
23 Correct 245 ms 25424 KB Output is correct
24 Correct 211 ms 25164 KB Output is correct
25 Correct 462 ms 27220 KB Output is correct
26 Correct 255 ms 25796 KB Output is correct
27 Correct 256 ms 25680 KB Output is correct
28 Execution timed out 2029 ms 14932 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 3 ms 8644 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 5 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 98 ms 10836 KB Output is correct
12 Correct 249 ms 10832 KB Output is correct
13 Correct 34 ms 10952 KB Output is correct
14 Correct 39 ms 10880 KB Output is correct
15 Correct 600 ms 10832 KB Output is correct
16 Correct 53 ms 10832 KB Output is correct
17 Correct 57 ms 10812 KB Output is correct
18 Execution timed out 2087 ms 10064 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 3 ms 8644 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 5 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 198 ms 23384 KB Output is correct
12 Correct 207 ms 22868 KB Output is correct
13 Correct 194 ms 22340 KB Output is correct
14 Correct 178 ms 22356 KB Output is correct
15 Correct 255 ms 23376 KB Output is correct
16 Correct 201 ms 22608 KB Output is correct
17 Correct 200 ms 22352 KB Output is correct
18 Correct 918 ms 24280 KB Output is correct
19 Correct 197 ms 21508 KB Output is correct
20 Correct 242 ms 22920 KB Output is correct
21 Correct 343 ms 26196 KB Output is correct
22 Correct 338 ms 26448 KB Output is correct
23 Correct 245 ms 25424 KB Output is correct
24 Correct 211 ms 25164 KB Output is correct
25 Correct 462 ms 27220 KB Output is correct
26 Correct 255 ms 25796 KB Output is correct
27 Correct 256 ms 25680 KB Output is correct
28 Execution timed out 2029 ms 14932 KB Time limit exceeded
29 Halted 0 ms 0 KB -