Submission #143491

#	Time	Username	Problem	Language	Result	Execution time	Memory
143491		darkkcyan	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1322 ms	53672 KiB

snake_escaping

#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);
// }

struct query_string {
    llong data;
    query_string() {}
    query_string& operator= (const string& s) {
        data = 0;
        for (auto i = s.rbegin(); i != s.rend(); ++i)
            data = data << 2 | (*i == '?' ? 3 : (*i - '0'));
        return *this;
    }

    int operator[](size_t pos) {
        return (data >> pos >> pos) & 3;
    }
};

#define maxl 20
#define maxn (1 << maxl)
#define maxq 1000101
int l, n, q;
int toxic[maxn];
pair<query_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] == 3) 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) {
        string que; cin >> que;
        queries[i].xx = que;
        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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25