oj.uz

Submission #1050513

# Submission time Handle Problem Language Result Execution time Memory
1050513 2024-08-09T10:21:25 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 29268 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 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], sub[11*N], sup[11*N];

void solve() {
    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i) {
        char c; cin >> c;
        a[i] = (c - '0');
    }
    for (int i = 0; i < (1 << n); ++i) {
        sub[i] = a[i];
        sup[i] = a[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (((mask >> i) & 1)) {
                sub[mask] += sub[mask - (1 << i)];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int mask = (1 << n) - 1; mask >= 0; --mask) {
            if (!((mask >> i) & 1)) {
                sup[mask] += sup[mask + (1 << i)];
            }
        }
    }
    while (q--) {
        string s; cin >> s;
        map<char,int> cnt;
        for (char c: s) {
            ++cnt[c];
        }
        reverse(all(s));
        int mask = 0;
        map<char,vector<int>> v;
        for (int i = 0; i < n; ++i) {
            v[s[i]].pub(i);
            if (s[i] != '?') {
                mask += (1 << i)*(s[i] - '0');
            }
        }
        int ans = 0;
        if (cnt['?'] <= 6) {
            for (int mask1 = 0; mask1 < (1 << cnt['?']); ++mask1) {
                int nmask = mask;
                for (int i = 0; i < cnt['?']; ++i) {
                    if ((mask1 >> i) & 1) {
                        nmask += (1 << v['?'][i]);
                    }
                }
                ans += a[nmask];
            }
        }
        else if (cnt['1'] <= 6) {
            for (int i: v['?']) {
                mask += (1 << i);
            }
            for (int mask1 = 0; mask1 < (1 << cnt['1']); ++mask1) {
                int nmask = mask;
                for (int i = 0; i < cnt['1']; ++i) {
                    if ((mask1 >> i) & 1) {
                        nmask -= (1 << v['1'][i]);
                    }
                }
                if (__builtin_popcount(mask1) % 2) {
                    ans -= sub[nmask];
                }
                else {
                    ans += sub[nmask];
                }
            }
        }
        else {
            for (int mask1 = 0; mask1 < (1 << cnt['0']); ++mask1) {
                int nmask = mask;
                for (int i = 0; i < cnt['0']; ++i) {
                    if ((mask1 >> i) & 1) {
                        nmask += (1 << v['0'][i]);
                    }
                }
                if (__builtin_popcount(mask1) % 2) {
                    ans -= sup[nmask];
                }
                else {
                    ans += sup[nmask];
                }
            }
        }
        cout << ans << '\n';
    }
}
 
signed main() {
    speed;
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}
/*
НЕ ЗАХОДИТ РЕШЕНИЕ?
1) ПРОВЕРЬ НА ОЧЕВИДНЫЕ ОШИБКИ В КОДЕ
2) ПРОВЕРЬ НА ПЕРЕПОЛНЕНИЯ
3) УБЕДИСЬ В ПРАВИЛЬНОСТИ АЛГОРИТМА
*/

Compilation message

snake_escaping.cpp:26:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   26 | const int INF = 1000000000000000000;
      |                 ^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 997 ms 14540 KB Output is correct
12 Correct 948 ms 14076 KB Output is correct
13 Correct 574 ms 13396 KB Output is correct
14 Correct 572 ms 13284 KB Output is correct
15 Correct 1711 ms 14296 KB Output is correct
16 Correct 737 ms 13572 KB Output is correct
17 Correct 981 ms 13652 KB Output is correct
18 Correct 283 ms 15440 KB Output is correct
19 Correct 381 ms 12400 KB Output is correct
20 Correct 925 ms 13896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 997 ms 14540 KB Output is correct
12 Correct 948 ms 14076 KB Output is correct
13 Correct 574 ms 13396 KB Output is correct
14 Correct 572 ms 13284 KB Output is correct
15 Correct 1711 ms 14296 KB Output is correct
16 Correct 737 ms 13572 KB Output is correct
17 Correct 981 ms 13652 KB Output is correct
18 Correct 283 ms 15440 KB Output is correct
19 Correct 381 ms 12400 KB Output is correct
20 Correct 925 ms 13896 KB Output is correct
21 Correct 2000 ms 15700 KB Output is correct
22 Correct 902 ms 15696 KB Output is correct
23 Correct 873 ms 14932 KB Output is correct
24 Correct 781 ms 14676 KB Output is correct
25 Correct 666 ms 16704 KB Output is correct
26 Correct 990 ms 15188 KB Output is correct
27 Correct 1029 ms 14976 KB Output is correct
28 Correct 281 ms 17744 KB Output is correct
29 Correct 429 ms 13648 KB Output is correct
30 Correct 1399 ms 15720 KB Output is correct
31 Correct 1841 ms 15736 KB Output is correct
32 Correct 1120 ms 15700 KB Output is correct
33 Correct 625 ms 14612 KB Output is correct
34 Correct 791 ms 14600 KB Output is correct
35 Correct 989 ms 15108 KB Output is correct
36 Correct 264 ms 13652 KB Output is correct
37 Correct 1868 ms 15700 KB Output is correct
38 Correct 506 ms 13648 KB Output is correct
39 Correct 838 ms 14932 KB Output is correct
40 Correct 778 ms 14564 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 51 ms 14772 KB Output is correct
12 Correct 57 ms 14616 KB Output is correct
13 Correct 85 ms 14672 KB Output is correct
14 Correct 137 ms 14420 KB Output is correct
15 Correct 73 ms 14612 KB Output is correct
16 Correct 117 ms 14416 KB Output is correct
17 Correct 99 ms 14420 KB Output is correct
18 Correct 38 ms 14676 KB Output is correct
19 Correct 50 ms 14428 KB Output is correct
20 Correct 61 ms 14676 KB Output is correct
21 Correct 89 ms 14636 KB Output is correct
22 Correct 139 ms 14416 KB Output is correct
23 Correct 71 ms 14420 KB Output is correct
24 Correct 127 ms 14620 KB Output is correct
25 Correct 100 ms 14416 KB Output is correct
26 Correct 38 ms 14420 KB Output is correct
27 Correct 58 ms 14600 KB Output is correct
28 Correct 51 ms 14532 KB Output is correct
29 Correct 92 ms 14548 KB Output is correct
30 Correct 127 ms 14452 KB Output is correct
31 Correct 70 ms 14420 KB Output is correct
32 Correct 126 ms 14416 KB Output is correct
33 Correct 99 ms 14644 KB Output is correct
34 Correct 39 ms 14420 KB Output is correct
35 Correct 87 ms 14420 KB Output is correct
36 Correct 89 ms 14532 KB Output is correct
37 Correct 98 ms 14404 KB Output is correct
38 Correct 85 ms 14508 KB Output is correct
39 Correct 88 ms 14468 KB Output is correct
40 Correct 92 ms 14608 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 997 ms 14540 KB Output is correct
12 Correct 948 ms 14076 KB Output is correct
13 Correct 574 ms 13396 KB Output is correct
14 Correct 572 ms 13284 KB Output is correct
15 Correct 1711 ms 14296 KB Output is correct
16 Correct 737 ms 13572 KB Output is correct
17 Correct 981 ms 13652 KB Output is correct
18 Correct 283 ms 15440 KB Output is correct
19 Correct 381 ms 12400 KB Output is correct
20 Correct 925 ms 13896 KB Output is correct
21 Correct 2000 ms 15700 KB Output is correct
22 Correct 902 ms 15696 KB Output is correct
23 Correct 873 ms 14932 KB Output is correct
24 Correct 781 ms 14676 KB Output is correct
25 Correct 666 ms 16704 KB Output is correct
26 Correct 990 ms 15188 KB Output is correct
27 Correct 1029 ms 14976 KB Output is correct
28 Correct 281 ms 17744 KB Output is correct
29 Correct 429 ms 13648 KB Output is correct
30 Correct 1399 ms 15720 KB Output is correct
31 Correct 1841 ms 15736 KB Output is correct
32 Correct 1120 ms 15700 KB Output is correct
33 Correct 625 ms 14612 KB Output is correct
34 Correct 791 ms 14600 KB Output is correct
35 Correct 989 ms 15108 KB Output is correct
36 Correct 264 ms 13652 KB Output is correct
37 Correct 1868 ms 15700 KB Output is correct
38 Correct 506 ms 13648 KB Output is correct
39 Correct 838 ms 14932 KB Output is correct
40 Correct 778 ms 14564 KB Output is correct
41 Correct 51 ms 14772 KB Output is correct
42 Correct 57 ms 14616 KB Output is correct
43 Correct 85 ms 14672 KB Output is correct
44 Correct 137 ms 14420 KB Output is correct
45 Correct 73 ms 14612 KB Output is correct
46 Correct 117 ms 14416 KB Output is correct
47 Correct 99 ms 14420 KB Output is correct
48 Correct 38 ms 14676 KB Output is correct
49 Correct 50 ms 14428 KB Output is correct
50 Correct 61 ms 14676 KB Output is correct
51 Correct 89 ms 14636 KB Output is correct
52 Correct 139 ms 14416 KB Output is correct
53 Correct 71 ms 14420 KB Output is correct
54 Correct 127 ms 14620 KB Output is correct
55 Correct 100 ms 14416 KB Output is correct
56 Correct 38 ms 14420 KB Output is correct
57 Correct 58 ms 14600 KB Output is correct
58 Correct 51 ms 14532 KB Output is correct
59 Correct 92 ms 14548 KB Output is correct
60 Correct 127 ms 14452 KB Output is correct
61 Correct 70 ms 14420 KB Output is correct
62 Correct 126 ms 14416 KB Output is correct
63 Correct 99 ms 14644 KB Output is correct
64 Correct 39 ms 14420 KB Output is correct
65 Correct 87 ms 14420 KB Output is correct
66 Correct 89 ms 14532 KB Output is correct
67 Correct 98 ms 14404 KB Output is correct
68 Correct 85 ms 14508 KB Output is correct
69 Correct 88 ms 14468 KB Output is correct
70 Correct 92 ms 14608 KB Output is correct
71 Correct 629 ms 28944 KB Output is correct
72 Correct 739 ms 29268 KB Output is correct
73 Correct 1290 ms 27616 KB Output is correct
74 Execution timed out 2037 ms 26108 KB Time limit exceeded
75 Halted 0 ms 0 KB -