Submission #1126054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126054		patgra	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1514 ms	26396 KiB

snake_escaping

#include <iostream>
#include <vector>

#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;
int arr[maxn];
vector<int> sosDown(maxn), sosUp(maxn);
string str;
int mask0, mask1, maskQ;

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

void preprocess() {
    vector<int> sosTmp1(maxn), sosTmp2(maxn);
    rep(i, 0, 1 << l) sosTmp2[i] = arr[i];
    rep(i, 1, l + 1) {
        swap(sosTmp1, sosTmp2);
        rep(mask, 0, 1 << l) sosTmp2[mask] = sosTmp1[mask] + ((mask & (1 << (i - 1))) ? (sosTmp1[mask ^ (1 << (i - 1))]) : 0);
    }
    swap(sosTmp2, sosDown);
    rep(i, 0, 1 << l) sosTmp2[i] = arr[i];
    rep(i, 1, l + 1) {
        swap(sosTmp1, sosTmp2);
        rep(mask, 0, 1 << l) sosTmp2[mask] = sosTmp1[mask] + ((mask & (1 << (i - 1))) ? 0 : (sosTmp1[mask ^ (1 << (i - 1))]));
    }
    swap(sosTmp2, sosUp);
    DEBUG {
        DC << "SOS DOWN: " << eol;
        rep(mask, 0, 1 << l) DC << sosDown[mask] << ' '; DC << eol;
        DC << "SOS UP: " << eol;
        rep(mask, 0, 1 << l) DC << sosUp[mask] << ' '; DC << eol;
    }
}

ll pala1() {
    // DC << " p1:" << eol;
    ll ans = 0;
    auto myMaskQ = maskQ;
    // DC << "  " << myMaskQ << " | " << mask1 << eol;
    ans += arr[myMaskQ | mask1];
    while (myMaskQ) {
        myMaskQ = (myMaskQ - 1) & maskQ;
        ans += arr[myMaskQ | mask1];
        // DC << "  " << myMaskQ << " | " << mask1 << eol;
    }
    return ans;
}

ll pala2() {
    ll ans = 0;
    int myMask1 = mask1;
    ans += sosDown[maskQ | myMask1];
    while (myMask1) {
        myMask1 = (myMask1 - 1) & mask1;
        ans += sosDown[maskQ | myMask1] * ((__builtin_popcount(mask1) - __builtin_popcount(myMask1)) % 2 == 0 ? 1 : -1);
    }
    return ans;
}

ll pala3() {
    ll ans = 0;
    auto myMask0 = mask0;
    ans += sosUp[mask1 | myMask0] * (__builtin_popcount(myMask0) % 2 == 0 ? 1 : -1);
    while (myMask0) {
        myMask0 = (myMask0 - 1) & mask0;
        ans += sosUp[mask1 | myMask0] * (__builtin_popcount(myMask0) % 2 == 0 ? 1 : -1);
    }
    return ans;
}

void processQueries() {
    str.resize(l);
    rep(i, 0, q) {
        rep(j, 0, l) scanf(" %c", &str[l - j - 1]);
        mask1 = mask0 = maskQ = 0;
        int j = 0; repIn(c, str) (c == '1' ? mask1 : c == '0' ? mask0 : maskQ) |= 1 << j++;
        DC << str << ' ' << mask0 << ' ' << mask1 << ' ' << maskQ << eol;
        // printf("odp: %lld %lld %lld\n", pala1(), pala2(), pala3());
        // continue;
        if (__builtin_popcount(maskQ) <= xd) printf("%lld\n", pala1());
        else if (__builtin_popcount(mask1) <= xd) printf("%lld\n", pala2());
        else printf("%lld\n", pala3());
    }
}

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

Compilation message (stderr)

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

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