oj.uz

Submission #110089

# Submission time Handle Problem Language Result Execution time Memory
110089 2019-05-09T12:24:23 Z popovicirobert Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 15224 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)];
            }
        }
    }

    while(q > 0) {
        q--;

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

        int cnf = 0, num = 0;
        for(i = 0; i < l; i++) {
            if(cur[i] == '1') {
                cnf += (1 << i);
            }
            if(cur[i] == '?') {
                num++;
            }
        }

        vector <int> bit;

        if(num <= 10) {

            int ans = 0;

            for(i = 0; i < l; i++) {
                if(cur[i] == '?') {
                    bit.push_back(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';
            }

            cout << ans << "\n";
        }
        else {

            int ans = 0;

            for(i = 0; i < l; i++) {
                if(str[i] == '1') {
                    bit.push_back(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];
                }

            }

            cout << ans << "\n";
        }

    }

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 57 ms 476 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 786 ms 15196 KB Output is correct
12 Correct 1836 ms 14840 KB Output is correct
13 Correct 463 ms 14104 KB Output is correct
14 Correct 445 ms 14072 KB Output is correct
15 Correct 1121 ms 15224 KB Output is correct
16 Correct 635 ms 14480 KB Output is correct
17 Correct 716 ms 14240 KB Output is correct
18 Execution timed out 2051 ms 1348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 57 ms 476 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 786 ms 15196 KB Output is correct
12 Correct 1836 ms 14840 KB Output is correct
13 Correct 463 ms 14104 KB Output is correct
14 Correct 445 ms 14072 KB Output is correct
15 Correct 1121 ms 15224 KB Output is correct
16 Correct 635 ms 14480 KB Output is correct
17 Correct 716 ms 14240 KB Output is correct
18 Execution timed out 2051 ms 1348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 57 ms 476 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 786 ms 15196 KB Output is correct
12 Correct 1836 ms 14840 KB Output is correct
13 Correct 463 ms 14104 KB Output is correct
14 Correct 445 ms 14072 KB Output is correct
15 Correct 1121 ms 15224 KB Output is correct
16 Correct 635 ms 14480 KB Output is correct
17 Correct 716 ms 14240 KB Output is correct
18 Execution timed out 2051 ms 1348 KB Time limit exceeded
19 Halted 0 ms 0 KB -