oj.uz

Submission #1050398

# Submission time Handle Problem Language Result Execution time Memory
1050398 2024-08-09T09:05:29 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 133 ms 24400 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define static_assert(...);
#include <tr2/dynamic_bitset>
using custom_bitset = tr2::dynamic_bitset<__uint128_t>;
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define bigInt __int128
#define dl double long
#define fl float
#define all(s) s.begin(), s.end()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pob_front
#define ins insert
#define F first
#define S second
#define len length
const int N = 100010;
const int M = 1010;
const int LN = 131072;
const int INF = 1000000000000000000;
const int MOD = 1e9 + 7;
const int BLOCK = 500;
int binpow(int a, int b, int MOD) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a;
            res %= MOD;
        }
        a = a * a;
        a %= MOD;
        b >>= 1;
    }
    return res;
}
int MMI(int a, int MOD) {
    int ret = binpow(a, MOD - 2, MOD);
    return ret;
}
// int mdiv(int a, int b) {
//     int ret = a*MMI(b);
//     ret %= MOD;
//     return ret;
// }
int mmul(int a, int b) {
    int ret = (a % MOD) * (b % MOD);
    ret %= MOD;
    return ret;
}
int madd(int a, int b) {
    int ret = (a % MOD) + (b % MOD);
    ret %= MOD;
    return ret;
}
int msub(int a, int b) {
    int ret = (a % MOD) - (b % MOD);
    ret += MOD;
    ret %= MOD;
    return ret;
}
int GCD(int a, int b) {
    if (b == 0) {
        return a;
    }
    return GCD(b, a % b);
}
int LCM(int a, int b) {
    return a*b / GCD(a, b);
}
struct pqComp
{
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) const
    {
        return (p1.F < p2.F) || (p1.F == p2.F && p1.S < p2.S);
    }
};
bool pCompF(pair<int, int>& p1, pair<int, int>& p2)
{
    return p1.F < p2.F;
}
bool pCompS(pair<int, int>& p1, pair<int, int>& p2)
{
    return p1.S < p2.S;
}
bool pCompFS(pair<int, int>& p1, pair<int, int>& p2)
{
    return (p1.S < p2.S) || (p1.S == p2.S && p1.F < p2.F);
}
vector <pair<int, int>> DS {{1, 0}, {0, 1}};//{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};//, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int n, q, a[11*N], dp[(1 << 10)][(1 << 10)];

void solve() {
    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i) {
        char c; cin >> c;
        a[i] = (c - '0');
    }
    if (n <= 10) {
        for (int mask1 = 0; mask1 < (1 << n); ++mask1) {
            for (int i = 0; i < (1 << n); ++i) {
                if ((mask1 & i)) continue;
                dp[mask1][i] = a[mask1 + i];
            }
            for (int i = 0; i < n; ++i) {
                for (int mask2 = 0; mask2 < (1 << n); ++mask2) {
                    if ((mask1 & mask2)) continue;
                    if ((mask2 >> i) & 1) {
                        dp[mask1][mask2] += dp[mask1][mask2 - (1 << i)];
                    }
                }
            }
        }
        while (q--) {
            string s; cin >> s;
            reverse(all(s));
            int mask1 = 0, mask2 = 0;
            for (int i = 0; i < n; ++i) {
                if (s[i] == '?') {
                    mask2 += (1 << i);
                }
                else {
                    mask1 += (1 << i)*(s[i] - '0');
                }
            }
            cout << dp[mask1][mask2] << '\n';
        }
    }
}
 
signed main() {
    speed;
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}
/*
НЕ ЗАХОДИТ РЕШЕНИЕ?
1) ПРОВЕРЬ НА ОЧЕВИДНЫЕ ОШИБКИ В КОДЕ
2) ПРОВЕРЬ НА ПЕРЕПОЛНЕНИЯ
3) УБЕДИСЬ В ПРАВИЛЬНОСТИ АЛГОРИТМА
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 4 ms 8832 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Correct 122 ms 21272 KB Output is correct
12 Correct 122 ms 23028 KB Output is correct
13 Correct 113 ms 22316 KB Output is correct
14 Correct 116 ms 22356 KB Output is correct
15 Correct 116 ms 23476 KB Output is correct
16 Correct 117 ms 22524 KB Output is correct
17 Correct 123 ms 22492 KB Output is correct
18 Correct 88 ms 24400 KB Output is correct
19 Correct 87 ms 21588 KB Output is correct
20 Correct 133 ms 23124 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 4 ms 8832 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Correct 122 ms 21272 KB Output is correct
12 Correct 122 ms 23028 KB Output is correct
13 Correct 113 ms 22316 KB Output is correct
14 Correct 116 ms 22356 KB Output is correct
15 Correct 116 ms 23476 KB Output is correct
16 Correct 117 ms 22524 KB Output is correct
17 Correct 123 ms 22492 KB Output is correct
18 Correct 88 ms 24400 KB Output is correct
19 Correct 87 ms 21588 KB Output is correct
20 Correct 133 ms 23124 KB Output is correct
21 Incorrect 1 ms 2392 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 4 ms 8832 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Incorrect 9 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 4 ms 8832 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Correct 122 ms 21272 KB Output is correct
12 Correct 122 ms 23028 KB Output is correct
13 Correct 113 ms 22316 KB Output is correct
14 Correct 116 ms 22356 KB Output is correct
15 Correct 116 ms 23476 KB Output is correct
16 Correct 117 ms 22524 KB Output is correct
17 Correct 123 ms 22492 KB Output is correct
18 Correct 88 ms 24400 KB Output is correct
19 Correct 87 ms 21588 KB Output is correct
20 Correct 133 ms 23124 KB Output is correct
21 Incorrect 1 ms 2392 KB Output isn't correct
22 Halted 0 ms 0 KB -