Submission #523644

#	Time	Username	Problem	Language	Result	Execution time	Memory
523644		LptN21	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	840 ms	24444 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define FIRSTBIT(x) __builtin_ctzll(x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;

/* */
template<class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template<class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 1e9 + 7, M = 20;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;

int l, q;

int sumPar[MASK(M)]; // sum of toxicity of parent mask
int sumSub[MASK(M)]; // sum of toxicity of submask
int a[MASK(M)];

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d\n", &l, &q);
    char ch[MASK(l)]; scanf("%s\n", &ch);
    for(int i=0;i<MASK(l);i++) {
        a[i] = ch[i]-'0';
        sumSub[i] = a[i];
        sumPar[i] = a[i];
    }

    for(int j=0;j<l;j++) for(int i=0;i<MASK(l);i++) {
        if(BIT(i, j)) sumSub[i]+= sumSub[i^MASK(j)];
    }
    for(int j=0;j<l;j++) for(int i=0;i<MASK(l);i++) {
        if(!BIT(i, j)) sumPar[i]+= sumPar[i|MASK(j)];
    }

    for(int i=1;i<=q;i++) {
        scanf("%s\n", &ch);
        // 0, 1, ?
        int cnt[3]{0, 0, 0}, msk[3]{0, 0, 0};
        for(int j=0;j<l;j++) {
            if(ch[j]=='0') cnt[0]++, msk[0]|=MASK(l-j-1);
            if(ch[j]=='1') cnt[1]++, msk[1]|=MASK(l-j-1);
            if(ch[j]=='?') cnt[2]++, msk[2]|=MASK(l-j-1);
        }
        int mn = *min_element(cnt, cnt+3), ans = 0;

        if(cnt[0] == mn) { // 0
            for(int i=msk[0];i>=0;i=(i-1)&msk[0]) {
                ans+= (ODDBIT(i)?-1:1)*sumPar[i|msk[1]];
                if(i == 0) break;
            }
        } else if(cnt[1] == mn) {
            int oddbase = ODDBIT(msk[1]);
            for(int i=msk[1];i>=0;i=(i-1)&msk[1]) {
                ans+= (oddbase==ODDBIT(i)?1:-1)*sumSub[i|msk[2]];
                if(i == 0) break;
            }
        } else if(cnt[2] == mn) {
            for(int i=msk[2];i>=0;i=(i-1)&msk[2]) {
                ans+= a[i|msk[1]];
                if(i == 0) break;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:57:31: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[(1 << l)]' [-Wformat=]
   57 |     char ch[MASK(l)]; scanf("%s\n", &ch);
      |                              ~^     ~~~
      |                               |     |
      |                               char* char (*)[(1 << l)]
snake_escaping.cpp:72:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[(1 << l)]' [-Wformat=]
   72 |         scanf("%s\n", &ch);
      |                ~^     ~~~
      |                 |     |
      |                 char* char (*)[(1 << l)]
snake_escaping.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d%d\n", &l, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
snake_escaping.cpp:57:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     char ch[MASK(l)]; scanf("%s\n", &ch);
      |                       ~~~~~^~~~~~~~~~~~~
snake_escaping.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%s\n", &ch);
      |         ~~~~~^~~~~~~~~~~~~

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