Submission #860613

#	Time	Username	Problem	Language	Result	Execution time	Memory
860613		green_gold_dog	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	604 KiB

snake_escaping

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
ll FIR = 7, SEC = 13;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

void solve() {
        ll l, q;
        cin >> l >> q;
        if (FIR > l) {
                FIR = l;
        }
        SEC = l - FIR;
        vector<ll> ans(q, 0);
        vector<ll> arr(1 << l, 0);
        for (ll i = 0; i < (1 << l); i++) {
                char c;
                cin >> c;
                arr[i] = c - '0';
        }
        vector<vector<pair<ll, ll>>> all(1 << FIR);
        vector<ll> o1(q), o0(q);
        for (ll i = 0; i < q; i++) {
                string s;
                cin >> s;
                reverse(s.begin(), s.end());
                for (ll j = 0; j < FIR; j++) {
                        if (s[j] == '1') {
                                o1[i] += (1 << j);
                                o0[i] += (1 << j);
                        }
                        if (s[j] == '0') {
                                o1[i] += (1 << j);
                        }
                        if (s[j] == '?') {
                                o0[i] += (1 << j);
                        }
                }
                ll x = 0;
                for (ll j = FIR; j < l; j++) {
                        x *= 3;
                        if (s[j] == '1') {
                                x++;
                        }
                        if (s[j] == '?') {
                                x += 2;
                        }
                }
                all[o1[i] & o0[i]].emplace_back(i, x);
        }
        vector<ll> p3(1, 0);
        ll mx = 1;
        for (ll i = 0; i < SEC; i++) {
                p3.push_back(mx);
                mx *= 3;
        }
        vector<pair<ll, ll>> aa;
        for (ll i = 0; i < mx; i++) {
                ll col = 0;
                ll now = i;
                while (now) {
                        col += now % 3 == 2;
                        now /= 3;
                }
                aa.emplace_back(col, i);
        }
        sort(aa.begin(), aa.end());
        for (auto&[col, i] : aa) {
                col = 0;
                ll now = i;
                for (ll j = 0; j < SEC; j++) {
                        if (now % 3 == 2) {
                                col = j + 1;
                                break;
                        }
                        now /= 3;
                }
                if (col == 0) {
                        now = i;
                        for (ll j = SEC - 1; j >= 0; j--) {
                                if (now % 3 == 1) {
                                        col -= 1 << j;
                                }
                                now /= 3;
                        }
                }
        }
        vector<ll> dp(mx, 0);
        for (ll i = 0; i < (1 << FIR); i++) {
                for (auto[fir, j] : aa) {
                        if (fir <= 0) {
                                fir = -fir;
                                dp[j] = arr[(fir << FIR) + i];
                        } else {
                                dp[j] = dp[j - p3[fir]] + dp[j - p3[fir] * 2];
                        }
                }
                for (auto[j, k] : all[i]) {
                        ans[j] += dp[k];
                        if ((1 << l) - 1 != (i | o1[j])) {
                                all[(((i | o1[j]) + 1) | o1[j]) & o0[j]].emplace_back(j, k);
                        }
                }
                all[i].clear();
                all[i].shrink_to_fit();
        }
        for (auto i : ans) {
                cout << i << '\n';
        }
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message (stderr)

snake_escaping.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   12 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:158:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:159:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25