Submission #1125939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125939		patgra	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	1680 ms	131072 KiB

snake_escaping

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)

#define ll long long

constexpr bool dbg = false;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

using namespace std;

constexpr int maxl = 20, maxn = 1 << maxl, xd = 6;
int l, q;
ll arr[maxn], sos[maxl + 1][maxn], sosUp[maxl + 1][maxn];
string str;

void input() {
    scanf("%d%d", &l, &q);
    rep(i, 0, 1 << l) scanf(" %c", arr + i), arr[i] -= '0';
}

void preprocess() {
    rep(i, 0, 1 << l) sos[0][i] = arr[i];
    rep(i, 1, l + 1) rep(mask, 0, 1 << l) sos[i][mask] = sos[i - 1][mask] + ((mask & (1 << (i - 1))) ? (sos[i - 1][mask ^ (1 << (i - 1))]) : 0);
    rep(i, 0, 1 << l) sosUp[0][i] = arr[i];
    rep(i, 1, l + 1) rep(mask, 0, 1 << l) sosUp[i][mask] = sosUp[i - 1][mask] + ((mask & (1 << (i - 1))) ? 0 : (sosUp[i - 1][mask ^ (1 << (i - 1))]));
    DEBUG {
        DC << "SOS: " << eol;
        rep(i, 0, l + 1) { DC << ' '; rep(mask, 0, 1 << l) DC << sos[i][mask] << ' '; DC << eol;}
        DC << "SOS UP: " << eol;
        rep(i, 0, l + 1) { DC << ' '; rep(mask, 0, 1 << l) DC << sosUp[i][mask] << ' '; DC << eol;}
    }
}

ll pala1() {
    vector<int> questionMarks;
    int mask = 0;
    ll ans = 0;
    rep(i, 0, l) {
        if (str[i] == '?') questionMarks.push_back(i);
        else mask |= (str[i] - '0') << i;
    }
    rep(i, 0, 1 << questionMarks.size()) {
        rep(j, 0, questionMarks.size()) if (i & (1 << j)) mask |= 1 << questionMarks[j];
        ans += arr[mask];
        rep(j, 0, questionMarks.size()) if (i & (1 << j)) mask ^= 1 << questionMarks[j];
    }
    return ans;
}

ll pala2() {
    DC << "Query " << str << ":" << eol;
    vector<int> ones;
    int mask = 0;
    rep(i, 0, l) {
        if (str[i] == '1') ones.push_back(i), mask |= 1 << i;
        if (str[i] == '?') mask |= 1 << i;
    }
    ll ans = 0;
    DC << " ones: "; DEBUG repIn(i, ones) DC << i << ' '; DC << eol;
    rep(maskOnes, 0, 1 << ones.size()) {
        rep(i, 0, ones.size()) if (maskOnes & (1 << i)) mask ^= 1 << ones[i];
        ans += sos[l][mask] * (__builtin_popcount(maskOnes) % 2 == 0 ? 1 : -1);
        DC << " Adding " << sos[l][mask] * (__builtin_popcount(maskOnes) % 2 == 0 ? 1 : -1) << " for mask " << mask << eol;
        rep(i, 0, ones.size()) if (maskOnes & (1 << i)) mask ^= 1 << ones[i];
    }
    return ans;
}

ll pala3() {
    vector<int> zeros;
    int mask = 0;
    rep(i, 0, l) {
        if (str[i] == '0') zeros.push_back(i);
        if (str[i] == '1') mask |= 1 << i;
    }
    ll ans = 0;
    rep(maskZeros, 0, 1 << zeros.size()) {
        rep(i, 0, zeros.size()) if (maskZeros & (1 << i)) mask ^= 1 << zeros[i];
        ans += sosUp[l][mask] * (__builtin_popcount(maskZeros) % 2 == 0 ? 1 : -1);
        rep(i, 0, zeros.size()) if (maskZeros & (1 << i)) mask ^= 1 << zeros[i];
    }
    return ans;
}

void processQueries() {
    str.resize(l);
    rep(i, 0, q) {
        rep(j, 0, l) scanf(" %c", &str[l - j - 1]);
        int cnt1 = 0, cnt0 = 0, cntQ = 0;
        repIn(c, str) (c == '1' ? cnt1 : c == '0' ? cnt0 : cntQ)++;
        if (cntQ <= xd) printf("%lld\n", pala1());
        else if (cnt1 <= xd) printf("%lld\n", pala2());
        else if (cnt0 <= xd) printf("%lld\n", pala3());
    }
}

int main() {
    input();
    preprocess();
    processQueries();
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void input()':
snake_escaping.cpp:24:32: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'long long int*' [-Wformat=]
   24 |     rep(i, 0, 1 << l) scanf(" %c", arr + i), arr[i] -= '0';
      |                               ~^   ~~~~~~~
      |                                |       |
      |                                char*   long long int*
      |                               %lld
snake_escaping.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d%d", &l, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:24:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     rep(i, 0, 1 << l) scanf(" %c", arr + i), arr[i] -= '0';
      |                       ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void processQueries()':
snake_escaping.cpp:94:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         rep(j, 0, l) scanf(" %c", &str[l - j - 1]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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