oj.uz

Submission #143485

# Submission time Handle Problem Language Result Execution time Memory
143485 2019-08-14T09:29:31 Z darkkcyan Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 471 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

#define maxl 21
#define maxn (1 << maxl)
#define maxq 1000101
int l, n, q;
int toxic[maxn];
pair<string, int*> queries[maxq];
int ans[maxq];

template<class ToxicIter, class QueryIter>
void solve(int level, ToxicIter beg_tox, ToxicIter end_tox, QueryIter beg_que, QueryIter end_que) {
    if (beg_que == end_que) return ;
    if (level == l) {
        assert(distance(beg_tox, end_tox) == 1);
        for (auto i = beg_que; i != end_que; ++i)
            *(i->yy) = *beg_tox;
        return ;
    }

    auto oneIter = beg_que, questionIter = end_que;
    for (auto i = beg_que; i != questionIter; ) {
        if (i->xx[level] == '?') swap(*i, *--questionIter);
        else if (i->xx[level] == '0') swap(*(i++), *(oneIter++));
        else ++i;
    }

    ToxicIter mid_tox = beg_tox;
    advance(mid_tox, distance(beg_tox, end_tox) / 2);

    solve(level + 1, beg_tox, mid_tox, beg_que, oneIter);
    solve(level + 1, mid_tox, end_tox, oneIter, questionIter);

    for (auto i = beg_tox, f = mid_tox; f != end_tox; ++i, ++f)
        *i += *f;

    solve(level + 1, beg_tox, mid_tox, questionIter, end_que);

    for (auto i = beg_tox, f = mid_tox; f != end_tox; ++i, ++f)
        *i -= *f;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> l >> q;
    n = 1 << l;
    {
        string s; cin >> s;
        rep(i, n) toxic[i] = s[i] - '0';
    }

    rep(i, q) {
        cin >> queries[i].xx;
        queries[i].yy = ans + i;
    }

    solve(0, toxic, toxic + n, queries, queries + q);

    rep(i, q) cout << ans[i] << '\n';

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 36 ms 39544 KB Output is correct
3 Correct 36 ms 39544 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 36 ms 39672 KB Output is correct
6 Correct 36 ms 39544 KB Output is correct
7 Correct 36 ms 39544 KB Output is correct
8 Correct 36 ms 39544 KB Output is correct
9 Correct 36 ms 39548 KB Output is correct
10 Correct 37 ms 39548 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 36 ms 39544 KB Output is correct
3 Correct 36 ms 39544 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 36 ms 39672 KB Output is correct
6 Correct 36 ms 39544 KB Output is correct
7 Correct 36 ms 39544 KB Output is correct
8 Correct 36 ms 39544 KB Output is correct
9 Correct 36 ms 39548 KB Output is correct
10 Correct 37 ms 39548 KB Output is correct
11 Correct 309 ms 58252 KB Output is correct
12 Correct 361 ms 57848 KB Output is correct
13 Correct 337 ms 57080 KB Output is correct
14 Correct 340 ms 57208 KB Output is correct
15 Correct 340 ms 58104 KB Output is correct
16 Correct 349 ms 57464 KB Output is correct
17 Correct 368 ms 57336 KB Output is correct
18 Correct 290 ms 59132 KB Output is correct
19 Correct 308 ms 56184 KB Output is correct
20 Correct 325 ms 57980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 36 ms 39544 KB Output is correct
3 Correct 36 ms 39544 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 36 ms 39672 KB Output is correct
6 Correct 36 ms 39544 KB Output is correct
7 Correct 36 ms 39544 KB Output is correct
8 Correct 36 ms 39544 KB Output is correct
9 Correct 36 ms 39548 KB Output is correct
10 Correct 37 ms 39548 KB Output is correct
11 Correct 309 ms 58252 KB Output is correct
12 Correct 361 ms 57848 KB Output is correct
13 Correct 337 ms 57080 KB Output is correct
14 Correct 340 ms 57208 KB Output is correct
15 Correct 340 ms 58104 KB Output is correct
16 Correct 349 ms 57464 KB Output is correct
17 Correct 368 ms 57336 KB Output is correct
18 Correct 290 ms 59132 KB Output is correct
19 Correct 308 ms 56184 KB Output is correct
20 Correct 325 ms 57980 KB Output is correct
21 Correct 338 ms 61180 KB Output is correct
22 Correct 397 ms 61432 KB Output is correct
23 Correct 411 ms 60280 KB Output is correct
24 Correct 392 ms 60152 KB Output is correct
25 Correct 389 ms 62168 KB Output is correct
26 Correct 430 ms 60664 KB Output is correct
27 Correct 471 ms 60664 KB Output is correct
28 Correct 323 ms 63224 KB Output is correct
29 Correct 343 ms 59128 KB Output is correct
30 Correct 367 ms 61432 KB Output is correct
31 Correct 419 ms 61276 KB Output is correct
32 Correct 394 ms 61180 KB Output is correct
33 Correct 334 ms 60024 KB Output is correct
34 Correct 421 ms 60120 KB Output is correct
35 Correct 459 ms 60536 KB Output is correct
36 Correct 265 ms 59244 KB Output is correct
37 Correct 373 ms 61272 KB Output is correct
38 Correct 362 ms 59128 KB Output is correct
39 Correct 392 ms 60408 KB Output is correct
40 Correct 380 ms 60220 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 36 ms 39544 KB Output is correct
3 Correct 36 ms 39544 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 36 ms 39672 KB Output is correct
6 Correct 36 ms 39544 KB Output is correct
7 Correct 36 ms 39544 KB Output is correct
8 Correct 36 ms 39544 KB Output is correct
9 Correct 36 ms 39548 KB Output is correct
10 Correct 37 ms 39548 KB Output is correct
11 Correct 90 ms 48388 KB Output is correct
12 Correct 95 ms 48488 KB Output is correct
13 Correct 227 ms 48388 KB Output is correct
14 Correct 249 ms 48476 KB Output is correct
15 Correct 176 ms 48520 KB Output is correct
16 Correct 264 ms 48364 KB Output is correct
17 Correct 256 ms 48388 KB Output is correct
18 Correct 67 ms 48644 KB Output is correct
19 Correct 92 ms 48288 KB Output is correct
20 Correct 94 ms 48392 KB Output is correct
21 Correct 231 ms 48488 KB Output is correct
22 Correct 250 ms 48368 KB Output is correct
23 Correct 172 ms 48424 KB Output is correct
24 Correct 250 ms 48388 KB Output is correct
25 Correct 272 ms 48392 KB Output is correct
26 Correct 62 ms 48264 KB Output is correct
27 Correct 95 ms 48388 KB Output is correct
28 Correct 94 ms 48232 KB Output is correct
29 Correct 225 ms 48388 KB Output is correct
30 Correct 248 ms 48552 KB Output is correct
31 Correct 177 ms 48388 KB Output is correct
32 Correct 258 ms 48388 KB Output is correct
33 Correct 257 ms 48388 KB Output is correct
34 Correct 71 ms 48260 KB Output is correct
35 Correct 240 ms 48396 KB Output is correct
36 Correct 234 ms 48544 KB Output is correct
37 Correct 231 ms 48392 KB Output is correct
38 Correct 231 ms 48392 KB Output is correct
39 Correct 241 ms 48376 KB Output is correct
40 Correct 244 ms 48488 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 36 ms 39544 KB Output is correct
3 Correct 36 ms 39544 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 36 ms 39672 KB Output is correct
6 Correct 36 ms 39544 KB Output is correct
7 Correct 36 ms 39544 KB Output is correct
8 Correct 36 ms 39544 KB Output is correct
9 Correct 36 ms 39548 KB Output is correct
10 Correct 37 ms 39548 KB Output is correct
11 Correct 309 ms 58252 KB Output is correct
12 Correct 361 ms 57848 KB Output is correct
13 Correct 337 ms 57080 KB Output is correct
14 Correct 340 ms 57208 KB Output is correct
15 Correct 340 ms 58104 KB Output is correct
16 Correct 349 ms 57464 KB Output is correct
17 Correct 368 ms 57336 KB Output is correct
18 Correct 290 ms 59132 KB Output is correct
19 Correct 308 ms 56184 KB Output is correct
20 Correct 325 ms 57980 KB Output is correct
21 Correct 338 ms 61180 KB Output is correct
22 Correct 397 ms 61432 KB Output is correct
23 Correct 411 ms 60280 KB Output is correct
24 Correct 392 ms 60152 KB Output is correct
25 Correct 389 ms 62168 KB Output is correct
26 Correct 430 ms 60664 KB Output is correct
27 Correct 471 ms 60664 KB Output is correct
28 Correct 323 ms 63224 KB Output is correct
29 Correct 343 ms 59128 KB Output is correct
30 Correct 367 ms 61432 KB Output is correct
31 Correct 419 ms 61276 KB Output is correct
32 Correct 394 ms 61180 KB Output is correct
33 Correct 334 ms 60024 KB Output is correct
34 Correct 421 ms 60120 KB Output is correct
35 Correct 459 ms 60536 KB Output is correct
36 Correct 265 ms 59244 KB Output is correct
37 Correct 373 ms 61272 KB Output is correct
38 Correct 362 ms 59128 KB Output is correct
39 Correct 392 ms 60408 KB Output is correct
40 Correct 380 ms 60220 KB Output is correct
41 Correct 90 ms 48388 KB Output is correct
42 Correct 95 ms 48488 KB Output is correct
43 Correct 227 ms 48388 KB Output is correct
44 Correct 249 ms 48476 KB Output is correct
45 Correct 176 ms 48520 KB Output is correct
46 Correct 264 ms 48364 KB Output is correct
47 Correct 256 ms 48388 KB Output is correct
48 Correct 67 ms 48644 KB Output is correct
49 Correct 92 ms 48288 KB Output is correct
50 Correct 94 ms 48392 KB Output is correct
51 Correct 231 ms 48488 KB Output is correct
52 Correct 250 ms 48368 KB Output is correct
53 Correct 172 ms 48424 KB Output is correct
54 Correct 250 ms 48388 KB Output is correct
55 Correct 272 ms 48392 KB Output is correct
56 Correct 62 ms 48264 KB Output is correct
57 Correct 95 ms 48388 KB Output is correct
58 Correct 94 ms 48232 KB Output is correct
59 Correct 225 ms 48388 KB Output is correct
60 Correct 248 ms 48552 KB Output is correct
61 Correct 177 ms 48388 KB Output is correct
62 Correct 258 ms 48388 KB Output is correct
63 Correct 257 ms 48388 KB Output is correct
64 Correct 71 ms 48260 KB Output is correct
65 Correct 240 ms 48396 KB Output is correct
66 Correct 234 ms 48544 KB Output is correct
67 Correct 231 ms 48392 KB Output is correct
68 Correct 231 ms 48392 KB Output is correct
69 Correct 241 ms 48376 KB Output is correct
70 Correct 244 ms 48488 KB Output is correct
71 Runtime error 145 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Halted 0 ms 0 KB -