oj.uz

Submission #536035

# Submission time Handle Problem Language Result Execution time Memory
536035 2022-03-12T07:34:52 Z Evang Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 20564 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 20;
const int MM = 1<<N;
int n, q, ar[MM], sub[MM], sup[MM];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> q;
    for(int i = 0; i < (1<<n); ++i) {
        char c;
        cin >> c;
        sub[i] = sup[i] = ar[i] = c-'0';
    }

    for(int i = 0; i < n; ++i){
        for(int j = 1; j < (1<<n); ++j)
            if((j>>i)&1)
                sub[j] += sub[j^(1<<i)];
        for(int j = (1<<n)-1; j >= 0; --j)
            if((j>>i)&1^1)
                sup[j] += sup[j^(1<<i)];
    }

#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 0; i < (1<<n); ++i)
        clog << bitset<N>(i) << sp << sub[i] << el;
    clog << el;
#endif

#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 0; i < (1<<n); ++i)
        clog << bitset<N>(i) << sp << sup[i] << el;
    clog << el;
#endif

    while(q--){
        str s;
        cin >> s;
        reverse(all(s));
        int a = 0, b = 0, c = 0;
        for(int i = 0; i < n; ++i){
            if(s[i]=='0')
                a |= 1<<i;
            else if(s[i]=='1')
                b |= 1<<i;
            else
                c |= 1<<i;
        }

        ll ans = 0;
        if(a==min({a, b, c})){
            for(int x = a;; x = (x-1)&a) {
                if (__builtin_popcount(x) & 1)
                    ans -= sup[b | x];
                else
                    ans += sup[b | x];

                if(x==0)
                    break;
            }
        }else if(b==min({a, b, c})){
            int b_cnt = __builtin_popcount(b);
            for(int x = b; ; x = (x-1)&b){
                if((b_cnt-__builtin_popcount(x))&1)
                    ans -= sub[c|x];
                else
                    ans += sub[c|x];
                if(x==0)
                    break;
            }
        }else{
            for(int x = c; ; x = (x-1)&c){
                ans += ar[b|x];
                if(x==0)
                    break;
            }
        }
        cout << ans << el;
    }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:90:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   90 |             if((j>>i)&1^1)
      |                ~~~~~~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 239 ms 4332 KB Output is correct
12 Correct 220 ms 4000 KB Output is correct
13 Correct 272 ms 3248 KB Output is correct
14 Correct 270 ms 3328 KB Output is correct
15 Correct 260 ms 4360 KB Output is correct
16 Correct 276 ms 3496 KB Output is correct
17 Correct 286 ms 3492 KB Output is correct
18 Correct 193 ms 5352 KB Output is correct
19 Correct 207 ms 2324 KB Output is correct
20 Correct 233 ms 3932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 239 ms 4332 KB Output is correct
12 Correct 220 ms 4000 KB Output is correct
13 Correct 272 ms 3248 KB Output is correct
14 Correct 270 ms 3328 KB Output is correct
15 Correct 260 ms 4360 KB Output is correct
16 Correct 276 ms 3496 KB Output is correct
17 Correct 286 ms 3492 KB Output is correct
18 Correct 193 ms 5352 KB Output is correct
19 Correct 207 ms 2324 KB Output is correct
20 Correct 233 ms 3932 KB Output is correct
21 Correct 239 ms 4352 KB Output is correct
22 Correct 284 ms 4540 KB Output is correct
23 Correct 391 ms 3540 KB Output is correct
24 Correct 329 ms 3388 KB Output is correct
25 Correct 307 ms 5328 KB Output is correct
26 Correct 336 ms 3900 KB Output is correct
27 Correct 340 ms 3860 KB Output is correct
28 Correct 183 ms 6444 KB Output is correct
29 Correct 227 ms 2352 KB Output is correct
30 Correct 259 ms 4524 KB Output is correct
31 Correct 331 ms 4364 KB Output is correct
32 Correct 305 ms 4424 KB Output is correct
33 Correct 334 ms 3316 KB Output is correct
34 Correct 348 ms 3424 KB Output is correct
35 Correct 337 ms 3900 KB Output is correct
36 Correct 180 ms 2428 KB Output is correct
37 Correct 232 ms 4388 KB Output is correct
38 Correct 249 ms 2364 KB Output is correct
39 Correct 333 ms 3600 KB Output is correct
40 Correct 331 ms 3428 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 78 ms 12832 KB Output is correct
12 Correct 80 ms 12756 KB Output is correct
13 Correct 140 ms 12740 KB Output is correct
14 Correct 127 ms 12744 KB Output is correct
15 Correct 122 ms 12908 KB Output is correct
16 Correct 117 ms 12744 KB Output is correct
17 Correct 146 ms 12804 KB Output is correct
18 Correct 68 ms 12996 KB Output is correct
19 Correct 84 ms 12628 KB Output is correct
20 Correct 74 ms 12864 KB Output is correct
21 Correct 118 ms 12816 KB Output is correct
22 Correct 118 ms 12744 KB Output is correct
23 Correct 173 ms 12748 KB Output is correct
24 Correct 137 ms 12744 KB Output is correct
25 Correct 123 ms 12744 KB Output is correct
26 Correct 66 ms 12620 KB Output is correct
27 Correct 82 ms 12872 KB Output is correct
28 Correct 81 ms 12628 KB Output is correct
29 Correct 136 ms 12744 KB Output is correct
30 Correct 133 ms 12796 KB Output is correct
31 Correct 182 ms 12652 KB Output is correct
32 Correct 136 ms 12744 KB Output is correct
33 Correct 133 ms 12792 KB Output is correct
34 Correct 68 ms 12592 KB Output is correct
35 Correct 134 ms 12876 KB Output is correct
36 Correct 129 ms 12756 KB Output is correct
37 Correct 139 ms 12748 KB Output is correct
38 Correct 119 ms 12720 KB Output is correct
39 Correct 126 ms 12744 KB Output is correct
40 Correct 114 ms 12872 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 239 ms 4332 KB Output is correct
12 Correct 220 ms 4000 KB Output is correct
13 Correct 272 ms 3248 KB Output is correct
14 Correct 270 ms 3328 KB Output is correct
15 Correct 260 ms 4360 KB Output is correct
16 Correct 276 ms 3496 KB Output is correct
17 Correct 286 ms 3492 KB Output is correct
18 Correct 193 ms 5352 KB Output is correct
19 Correct 207 ms 2324 KB Output is correct
20 Correct 233 ms 3932 KB Output is correct
21 Correct 239 ms 4352 KB Output is correct
22 Correct 284 ms 4540 KB Output is correct
23 Correct 391 ms 3540 KB Output is correct
24 Correct 329 ms 3388 KB Output is correct
25 Correct 307 ms 5328 KB Output is correct
26 Correct 336 ms 3900 KB Output is correct
27 Correct 340 ms 3860 KB Output is correct
28 Correct 183 ms 6444 KB Output is correct
29 Correct 227 ms 2352 KB Output is correct
30 Correct 259 ms 4524 KB Output is correct
31 Correct 331 ms 4364 KB Output is correct
32 Correct 305 ms 4424 KB Output is correct
33 Correct 334 ms 3316 KB Output is correct
34 Correct 348 ms 3424 KB Output is correct
35 Correct 337 ms 3900 KB Output is correct
36 Correct 180 ms 2428 KB Output is correct
37 Correct 232 ms 4388 KB Output is correct
38 Correct 249 ms 2364 KB Output is correct
39 Correct 333 ms 3600 KB Output is correct
40 Correct 331 ms 3428 KB Output is correct
41 Correct 78 ms 12832 KB Output is correct
42 Correct 80 ms 12756 KB Output is correct
43 Correct 140 ms 12740 KB Output is correct
44 Correct 127 ms 12744 KB Output is correct
45 Correct 122 ms 12908 KB Output is correct
46 Correct 117 ms 12744 KB Output is correct
47 Correct 146 ms 12804 KB Output is correct
48 Correct 68 ms 12996 KB Output is correct
49 Correct 84 ms 12628 KB Output is correct
50 Correct 74 ms 12864 KB Output is correct
51 Correct 118 ms 12816 KB Output is correct
52 Correct 118 ms 12744 KB Output is correct
53 Correct 173 ms 12748 KB Output is correct
54 Correct 137 ms 12744 KB Output is correct
55 Correct 123 ms 12744 KB Output is correct
56 Correct 66 ms 12620 KB Output is correct
57 Correct 82 ms 12872 KB Output is correct
58 Correct 81 ms 12628 KB Output is correct
59 Correct 136 ms 12744 KB Output is correct
60 Correct 133 ms 12796 KB Output is correct
61 Correct 182 ms 12652 KB Output is correct
62 Correct 136 ms 12744 KB Output is correct
63 Correct 133 ms 12792 KB Output is correct
64 Correct 68 ms 12592 KB Output is correct
65 Correct 134 ms 12876 KB Output is correct
66 Correct 129 ms 12756 KB Output is correct
67 Correct 139 ms 12748 KB Output is correct
68 Correct 119 ms 12720 KB Output is correct
69 Correct 126 ms 12744 KB Output is correct
70 Correct 114 ms 12872 KB Output is correct
71 Correct 449 ms 17692 KB Output is correct
72 Correct 425 ms 17692 KB Output is correct
73 Correct 1509 ms 16420 KB Output is correct
74 Correct 1231 ms 16712 KB Output is correct
75 Correct 1127 ms 18600 KB Output is correct
76 Correct 1261 ms 17128 KB Output is correct
77 Correct 1371 ms 16920 KB Output is correct
78 Correct 277 ms 20564 KB Output is correct
79 Correct 351 ms 14748 KB Output is correct
80 Correct 394 ms 17780 KB Output is correct
81 Correct 972 ms 17828 KB Output is correct
82 Correct 1195 ms 16592 KB Output is correct
83 Execution timed out 2094 ms 15936 KB Time limit exceeded
84 Halted 0 ms 0 KB -