제출 #252193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252193		Nightlight	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1654 ms	42312 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

int L, Q;
char ch;
int A[1 << 20];
int dp0[1 << 20];//1 jadi 1, semua 0 jadi ?
int dp1[1 << 20];//0 jadi 0, semua 1 jadi ?

int main() {
  ios_base::sync_with_stdio(0);
  cin >> L >> Q;
  for(int i = 0; i < (1 << L); i++) {
    cin >> ch;
    A[i] = ch - '0';
    dp0[i] = dp1[i] = A[i];
  }
  for(int i = 0; i < L; i++) {
    for(int mask = 0; mask < (1 << L); mask++) {
      if(mask & (1 << i)) {
        dp1[mask] += dp1[mask ^ (1 << i)];
      }else dp0[mask] += dp0[mask ^ (1 << i)];
    }
  }
//  cout << "-> " << dp0[0] << "\n";
//  cout << "-> " << dp0[(1 << L) - 1] << "\n";
  int mask1, mask0, maskq;
  int cnt1, cnt0, cntq;
  int ans, tmp, bit;
  while(Q--) {
    ans = mask1 = mask0 = maskq = cnt1 = cnt0 = cntq = 0;
    for(int i = L - 1; i >= 0; i--) {
      cin >> ch;
      if(ch == '0') mask0 |= (1 << i), cnt0++;
      if(ch == '1') mask1 |= (1 << i), cnt1++;
      if(ch == '?') maskq |= (1 << i), cntq++;
    }
    if(cntq <= cnt0 && cntq < cnt1) {
      tmp = maskq;
      while(tmp) {
//      	cout << Q << ": " << A[mask1 | tmp] << " " << A[mask1] << "\n";
        ans += A[mask1 | tmp];
        tmp = maskq & (tmp - 1);
      }
      printf("%d\n", ans + A[mask1]);
    }else if(cnt0 < cnt1) {
      tmp = mask0;
      while(tmp) {
        ans += dp0[mask1 | tmp] * (__builtin_popcount(tmp) & 1 ? -1 : 1);
        tmp = mask0 & (tmp - 1);
      }
      printf("%d\n", ans + dp0[mask1]);
    }else {
      tmp = mask1;
      while(tmp) {
        bit = ((((1 << L) - 1) ^ tmp) & (((1 << L) - 1) & mask1));
//        cout << tmp << " " << bit << " " << dp1[maskq | bit] << "\n";
        ans += dp1[maskq | bit] * (__builtin_popcount(bit) & 1 ? 1 : -1) * (__builtin_popcount(mask1) & 1 ? 1 : -1);;
        tmp = mask1 & (tmp - 1);
      }
      printf("%d\n", ans + dp1[maskq + mask1]);
    }
  };
}

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