oj.uz

Submission #110099

# Submission time Handle Problem Language Result Execution time Memory
110099 2019-05-09T12:48:06 Z popovicirobert Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 35308 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

int dp[1 << 20];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, l, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> l >> q;

    string str;
    cin >> str;

    for(int conf = 0; conf < (1 << l); conf++) {
        dp[conf] = str[conf] - '0';
    }
    for(int bit = 0; bit < l; bit++) {
        for(int conf = 0; conf < (1 << l); conf++) {
            if(conf & (1 << bit)) {
                dp[conf] += dp[conf ^ (1 << bit)];
            }
        }
    }

    unordered_map <int, int> mp;

    while(q > 0) {
        q--;

        string cur;
        cin >> cur;
        reverse(cur.begin(), cur.end());

        int numq = 0, num1 = 0, val = 0;
        for(i = 0; i < l; i++) {
            val *= 3;
            if(cur[i] == '?') {
                numq++;
                val += 2;
            }
            else {
                val += cur[i] - '0';
                num1 += cur[i] - '0';
            }
        }

        if(mp[val] > 0) {
            cout << mp[val] - 1 << "\n";
            continue;
        }

        vector <int> bit;

        if(numq <= num1) {

            int ans = 0, cnf = 0;

            for(i = 0; i < l; i++) {
                if(cur[i] == '?') {
                    bit.push_back(i);
                }
                if(cur[i] == '1') {
                    cnf ^= (1 << i);
                }
            }

            int sz = bit.size();
            for(int conf = 0; conf < (1 << sz); conf++) {
                int aux = cnf;
                for(i = 0; i < sz; i++) {
                    if(conf & (1 << i)) {
                        aux += (1 << bit[i]);
                    }
                }
                ans += str[aux] - '0';
            }

            mp[val] = ans + 1;
            cout << ans << "\n";
        }
        else {

            ll ans = 0;
            int cnf = 0;

            for(i = 0; i < l; i++) {
                if(cur[i] == '1') {
                    bit.push_back(i);
                }
                if(cur[i] != '0') {
                    cnf ^= (1 << i);
                }
            }

            int sz = bit.size();
            for(int conf = 0; conf < (1 << sz); conf++) {

                int aux = cnf, cnt = 0;
                for(i = 0; i < sz; i++) {
                    if(conf & (1 << i)) {
                        aux ^= (1 << bit[i]);
                        cnt++;
                    }
                }

                if(cnt & 1) {
                    ans -= dp[aux];
                }
                else {
                    ans += dp[aux];
                }

            }

            mp[val] = ans + 1;
            cout << ans << "\n";
        }

    }

    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 265 ms 5880 KB Output is correct
12 Correct 262 ms 5496 KB Output is correct
13 Correct 277 ms 5112 KB Output is correct
14 Correct 273 ms 5012 KB Output is correct
15 Correct 256 ms 5964 KB Output is correct
16 Correct 317 ms 5664 KB Output is correct
17 Correct 333 ms 7692 KB Output is correct
18 Correct 191 ms 6648 KB Output is correct
19 Correct 216 ms 3576 KB Output is correct
20 Correct 254 ms 5240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 265 ms 5880 KB Output is correct
12 Correct 262 ms 5496 KB Output is correct
13 Correct 277 ms 5112 KB Output is correct
14 Correct 273 ms 5012 KB Output is correct
15 Correct 256 ms 5964 KB Output is correct
16 Correct 317 ms 5664 KB Output is correct
17 Correct 333 ms 7692 KB Output is correct
18 Correct 191 ms 6648 KB Output is correct
19 Correct 216 ms 3576 KB Output is correct
20 Correct 254 ms 5240 KB Output is correct
21 Correct 258 ms 5624 KB Output is correct
22 Correct 308 ms 6172 KB Output is correct
23 Correct 799 ms 13024 KB Output is correct
24 Correct 639 ms 8072 KB Output is correct
25 Correct 524 ms 8160 KB Output is correct
26 Correct 959 ms 19132 KB Output is correct
27 Correct 1116 ms 35304 KB Output is correct
28 Correct 260 ms 7416 KB Output is correct
29 Correct 266 ms 3536 KB Output is correct
30 Correct 383 ms 5880 KB Output is correct
31 Correct 865 ms 13904 KB Output is correct
32 Correct 631 ms 9236 KB Output is correct
33 Correct 378 ms 5896 KB Output is correct
34 Correct 914 ms 18780 KB Output is correct
35 Correct 1150 ms 35308 KB Output is correct
36 Correct 217 ms 3328 KB Output is correct
37 Correct 342 ms 5372 KB Output is correct
38 Correct 277 ms 3548 KB Output is correct
39 Correct 739 ms 13112 KB Output is correct
40 Correct 553 ms 7832 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Execution timed out 2017 ms 8016 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 265 ms 5880 KB Output is correct
12 Correct 262 ms 5496 KB Output is correct
13 Correct 277 ms 5112 KB Output is correct
14 Correct 273 ms 5012 KB Output is correct
15 Correct 256 ms 5964 KB Output is correct
16 Correct 317 ms 5664 KB Output is correct
17 Correct 333 ms 7692 KB Output is correct
18 Correct 191 ms 6648 KB Output is correct
19 Correct 216 ms 3576 KB Output is correct
20 Correct 254 ms 5240 KB Output is correct
21 Correct 258 ms 5624 KB Output is correct
22 Correct 308 ms 6172 KB Output is correct
23 Correct 799 ms 13024 KB Output is correct
24 Correct 639 ms 8072 KB Output is correct
25 Correct 524 ms 8160 KB Output is correct
26 Correct 959 ms 19132 KB Output is correct
27 Correct 1116 ms 35304 KB Output is correct
28 Correct 260 ms 7416 KB Output is correct
29 Correct 266 ms 3536 KB Output is correct
30 Correct 383 ms 5880 KB Output is correct
31 Correct 865 ms 13904 KB Output is correct
32 Correct 631 ms 9236 KB Output is correct
33 Correct 378 ms 5896 KB Output is correct
34 Correct 914 ms 18780 KB Output is correct
35 Correct 1150 ms 35308 KB Output is correct
36 Correct 217 ms 3328 KB Output is correct
37 Correct 342 ms 5372 KB Output is correct
38 Correct 277 ms 3548 KB Output is correct
39 Correct 739 ms 13112 KB Output is correct
40 Correct 553 ms 7832 KB Output is correct
41 Execution timed out 2017 ms 8016 KB Time limit exceeded
42 Halted 0 ms 0 KB -