oj.uz

Submission #536034

# Submission time Handle Problem Language Result Execution time Memory
536034 2022-03-12T07:34:35 Z Evang Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 20588 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 235 ms 4260 KB Output is correct
12 Correct 227 ms 3968 KB Output is correct
13 Correct 271 ms 3260 KB Output is correct
14 Correct 261 ms 3336 KB Output is correct
15 Correct 265 ms 4288 KB Output is correct
16 Correct 267 ms 3532 KB Output is correct
17 Correct 295 ms 3380 KB Output is correct
18 Correct 226 ms 5324 KB Output is correct
19 Correct 196 ms 2400 KB Output is correct
20 Correct 237 ms 3928 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 235 ms 4260 KB Output is correct
12 Correct 227 ms 3968 KB Output is correct
13 Correct 271 ms 3260 KB Output is correct
14 Correct 261 ms 3336 KB Output is correct
15 Correct 265 ms 4288 KB Output is correct
16 Correct 267 ms 3532 KB Output is correct
17 Correct 295 ms 3380 KB Output is correct
18 Correct 226 ms 5324 KB Output is correct
19 Correct 196 ms 2400 KB Output is correct
20 Correct 237 ms 3928 KB Output is correct
21 Correct 267 ms 4396 KB Output is correct
22 Correct 230 ms 4524 KB Output is correct
23 Correct 374 ms 3524 KB Output is correct
24 Correct 323 ms 3380 KB Output is correct
25 Correct 265 ms 5372 KB Output is correct
26 Correct 318 ms 3916 KB Output is correct
27 Correct 376 ms 3792 KB Output is correct
28 Correct 173 ms 6436 KB Output is correct
29 Correct 228 ms 2384 KB Output is correct
30 Correct 231 ms 4592 KB Output is correct
31 Correct 315 ms 4420 KB Output is correct
32 Correct 343 ms 4508 KB Output is correct
33 Correct 314 ms 3312 KB Output is correct
34 Correct 348 ms 3424 KB Output is correct
35 Correct 351 ms 3896 KB Output is correct
36 Correct 199 ms 2388 KB Output is correct
37 Correct 228 ms 4440 KB Output is correct
38 Correct 247 ms 2420 KB Output is correct
39 Correct 355 ms 3528 KB Output is correct
40 Correct 339 ms 3412 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 87 ms 12800 KB Output is correct
12 Correct 73 ms 12752 KB Output is correct
13 Correct 147 ms 12744 KB Output is correct
14 Correct 132 ms 12744 KB Output is correct
15 Correct 122 ms 12872 KB Output is correct
16 Correct 138 ms 12772 KB Output is correct
17 Correct 146 ms 12792 KB Output is correct
18 Correct 79 ms 13004 KB Output is correct
19 Correct 91 ms 12616 KB Output is correct
20 Correct 77 ms 12868 KB Output is correct
21 Correct 132 ms 12864 KB Output is correct
22 Correct 137 ms 12744 KB Output is correct
23 Correct 177 ms 12744 KB Output is correct
24 Correct 130 ms 12744 KB Output is correct
25 Correct 140 ms 12740 KB Output is correct
26 Correct 77 ms 12612 KB Output is correct
27 Correct 80 ms 12872 KB Output is correct
28 Correct 82 ms 12624 KB Output is correct
29 Correct 130 ms 12756 KB Output is correct
30 Correct 137 ms 12744 KB Output is correct
31 Correct 186 ms 12744 KB Output is correct
32 Correct 131 ms 12824 KB Output is correct
33 Correct 183 ms 12748 KB Output is correct
34 Correct 77 ms 12640 KB Output is correct
35 Correct 130 ms 12748 KB Output is correct
36 Correct 128 ms 12740 KB Output is correct
37 Correct 163 ms 12744 KB Output is correct
38 Correct 128 ms 12812 KB Output is correct
39 Correct 117 ms 12724 KB Output is correct
40 Correct 141 ms 12740 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 235 ms 4260 KB Output is correct
12 Correct 227 ms 3968 KB Output is correct
13 Correct 271 ms 3260 KB Output is correct
14 Correct 261 ms 3336 KB Output is correct
15 Correct 265 ms 4288 KB Output is correct
16 Correct 267 ms 3532 KB Output is correct
17 Correct 295 ms 3380 KB Output is correct
18 Correct 226 ms 5324 KB Output is correct
19 Correct 196 ms 2400 KB Output is correct
20 Correct 237 ms 3928 KB Output is correct
21 Correct 267 ms 4396 KB Output is correct
22 Correct 230 ms 4524 KB Output is correct
23 Correct 374 ms 3524 KB Output is correct
24 Correct 323 ms 3380 KB Output is correct
25 Correct 265 ms 5372 KB Output is correct
26 Correct 318 ms 3916 KB Output is correct
27 Correct 376 ms 3792 KB Output is correct
28 Correct 173 ms 6436 KB Output is correct
29 Correct 228 ms 2384 KB Output is correct
30 Correct 231 ms 4592 KB Output is correct
31 Correct 315 ms 4420 KB Output is correct
32 Correct 343 ms 4508 KB Output is correct
33 Correct 314 ms 3312 KB Output is correct
34 Correct 348 ms 3424 KB Output is correct
35 Correct 351 ms 3896 KB Output is correct
36 Correct 199 ms 2388 KB Output is correct
37 Correct 228 ms 4440 KB Output is correct
38 Correct 247 ms 2420 KB Output is correct
39 Correct 355 ms 3528 KB Output is correct
40 Correct 339 ms 3412 KB Output is correct
41 Correct 87 ms 12800 KB Output is correct
42 Correct 73 ms 12752 KB Output is correct
43 Correct 147 ms 12744 KB Output is correct
44 Correct 132 ms 12744 KB Output is correct
45 Correct 122 ms 12872 KB Output is correct
46 Correct 138 ms 12772 KB Output is correct
47 Correct 146 ms 12792 KB Output is correct
48 Correct 79 ms 13004 KB Output is correct
49 Correct 91 ms 12616 KB Output is correct
50 Correct 77 ms 12868 KB Output is correct
51 Correct 132 ms 12864 KB Output is correct
52 Correct 137 ms 12744 KB Output is correct
53 Correct 177 ms 12744 KB Output is correct
54 Correct 130 ms 12744 KB Output is correct
55 Correct 140 ms 12740 KB Output is correct
56 Correct 77 ms 12612 KB Output is correct
57 Correct 80 ms 12872 KB Output is correct
58 Correct 82 ms 12624 KB Output is correct
59 Correct 130 ms 12756 KB Output is correct
60 Correct 137 ms 12744 KB Output is correct
61 Correct 186 ms 12744 KB Output is correct
62 Correct 131 ms 12824 KB Output is correct
63 Correct 183 ms 12748 KB Output is correct
64 Correct 77 ms 12640 KB Output is correct
65 Correct 130 ms 12748 KB Output is correct
66 Correct 128 ms 12740 KB Output is correct
67 Correct 163 ms 12744 KB Output is correct
68 Correct 128 ms 12812 KB Output is correct
69 Correct 117 ms 12724 KB Output is correct
70 Correct 141 ms 12740 KB Output is correct
71 Correct 400 ms 17564 KB Output is correct
72 Correct 431 ms 17728 KB Output is correct
73 Correct 1503 ms 16344 KB Output is correct
74 Correct 1421 ms 16560 KB Output is correct
75 Correct 1273 ms 18648 KB Output is correct
76 Correct 1489 ms 16952 KB Output is correct
77 Correct 1710 ms 16832 KB Output is correct
78 Correct 312 ms 20588 KB Output is correct
79 Correct 419 ms 14620 KB Output is correct
80 Correct 434 ms 17676 KB Output is correct
81 Correct 1388 ms 17580 KB Output is correct
82 Correct 1443 ms 16628 KB Output is correct
83 Execution timed out 2082 ms 15164 KB Time limit exceeded
84 Halted 0 ms 0 KB -