oj.uz

Submission #957934

# Submission time Handle Problem Language Result Execution time Memory
957934 2024-04-04T13:47:27 Z BhavayGoyal Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 635 ms 14672 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -------------------------------------------------- Main Code --------------------------------------------------

const int N = (1<<12)+5;
int n, q, arr[N], dp[12][N], dp2[12][N];

int getAns(string &s) {
    int num = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {num = -1; break;}
        else num += (1<<(n-i-1))*(s[i]-'0');
    }
    if (num != -1) {
        return arr[num];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            s[i] = '1';
            ans += getAns(s);
            s[i] = '0';
            ans += getAns(s);
            s[i] = '?';
            break;
        }
    }

    return ans;
}

int subSum(int idx, int mask) {
    if (idx < 0) return arr[mask];
    if (dp[idx][mask] != -1) return dp[idx][mask];
    int ans = subSum(idx-1, mask);
    if (mask&(1<<idx)) ans = (ans + subSum(idx-1, mask^(1<<idx)));
    return dp[idx][mask] = ans;
}

int subSum2(int idx, int mask) {
    if (idx < 0) return arr[mask];
    if (dp2[idx][mask] != -1) return dp2[idx][mask];
    int ans = subSum2(idx-1, mask);
    if ((mask&(1<<idx)) == 0) ans = (ans + subSum2(idx-1, mask^(1<<idx)));
    return dp2[idx][mask] = ans;
}

void sol() {
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp);
    cin >> n >> q;
    for (int i = 0; i < (1<<n); i++) {char x; cin >> x; arr[i] = x-'0';}

    while (q--) {
        string s; cin >> s;
        int one = 0, zero = 0, question = 0;
        for (int i = 0; i < n; i++) {
            one += s[i]=='1';
            zero += s[i]=='0';
            question += s[i]=='?';
        }

        if (zero <= 6) {
            vi temp;
            int num = 0;
            reverse(all(s));
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') temp.pb(i);
                if (s[i] == '1') num += (1<<i);
            }

            int ans = 0;
            for (int i = 0; i < (1<<temp.size()); i++) {
                int tempNum = num, ct = 0;
                for (int j = 0; j < temp.size(); j++) {
                    if ((i&(1<<j)) == 0) {
                        tempNum ^= (1<<temp[j]);
                        ct++;
                    }
                }
                if (ct%2 != 0) ans -= subSum2(n-1, tempNum);
                else ans += subSum2(n-1, tempNum);
            }

            cout << ans << endl;
        }
        else if (one <= 6) {
            vi temp;
            int num = 0;
            reverse(all(s));
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') temp.pb(i);
                if (s[i] == '1' || s[i] == '?') num += (1<<i);
            }

            int ans = 0;
            for (int i = 0; i < (1<<temp.size()); i++) {
                int tempNum = num, ct = 0;
                for (int j = 0; j < temp.size(); j++) {
                    if (i&(1<<j)) {
                        tempNum ^= (1<<temp[j]);
                        ct++;
                    }
                }
                if (ct%2 != 0) ans -= subSum(n-1, tempNum);
                else ans += subSum(n-1, tempNum);
            }

            cout << ans << endl;
        }
        else {
            cout << getAns(s) << endl;
        }
    }
}

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

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void sol()':
snake_escaping.cpp:106:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~
snake_escaping.cpp:130:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 200 ms 13772 KB Output is correct
12 Correct 521 ms 13396 KB Output is correct
13 Correct 635 ms 12720 KB Output is correct
14 Correct 410 ms 12684 KB Output is correct
15 Correct 297 ms 13848 KB Output is correct
16 Correct 357 ms 12916 KB Output is correct
17 Correct 444 ms 12944 KB Output is correct
18 Correct 154 ms 14672 KB Output is correct
19 Correct 572 ms 11632 KB Output is correct
20 Correct 206 ms 13392 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 200 ms 13772 KB Output is correct
12 Correct 521 ms 13396 KB Output is correct
13 Correct 635 ms 12720 KB Output is correct
14 Correct 410 ms 12684 KB Output is correct
15 Correct 297 ms 13848 KB Output is correct
16 Correct 357 ms 12916 KB Output is correct
17 Correct 444 ms 12944 KB Output is correct
18 Correct 154 ms 14672 KB Output is correct
19 Correct 572 ms 11632 KB Output is correct
20 Correct 206 ms 13392 KB Output is correct
21 Incorrect 1 ms 860 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 4 ms 3440 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 200 ms 13772 KB Output is correct
12 Correct 521 ms 13396 KB Output is correct
13 Correct 635 ms 12720 KB Output is correct
14 Correct 410 ms 12684 KB Output is correct
15 Correct 297 ms 13848 KB Output is correct
16 Correct 357 ms 12916 KB Output is correct
17 Correct 444 ms 12944 KB Output is correct
18 Correct 154 ms 14672 KB Output is correct
19 Correct 572 ms 11632 KB Output is correct
20 Correct 206 ms 13392 KB Output is correct
21 Incorrect 1 ms 860 KB Output isn't correct
22 Halted 0 ms 0 KB -