제출 #1242494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242494		LucasLe	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	503 ms	36564 KiB

snake_escaping

#include <bits/stdc++.h>

template<typename T>
bool minimize(T &x, T y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}

template<typename T>
bool maximize(T &x, T y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

const int MOD = 1e9 + 7;

template<typename T>
void add(T &x, T y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
}

#define fi first
#define se second
#define pii std::pair<int, int>

int N, Q;
std::string S;

int val[(1 << 20) + 5];
int sos_sub[(1 << 20) + 5], sos_super[(1 << 20) + 5];

void solve(int _t) {
  std::cin >> N >> Q;
  std::cin >> S;
  for (int i = 0; i < (1 << N); ++i) {
    val[i] = S[i] - '0';
    sos_sub[i] = val[i];
    sos_super[i] = val[i];
  }
  for (int i = 0; i < N; ++i) {
    for (int mask = 0; mask < (1 << N); ++mask) {
      if (mask & (1 << i)) 
        sos_sub[mask] += sos_sub[mask ^ (1 << i)];
      else
        sos_super[mask] += sos_super[mask ^ (1 << i)];
    }
  }
  while (Q--) {
    std::string s;
    std::cin >> s;
    int cntO = 0, maskO = 0;
    int cntZ = 0, maskZ = 0;
    int cntQ = 0, maskQ = 0;
    for (int i = 0; i < N; ++i) {
      if (s[i] == '1') {
        cntO++;
        maskO |= (1 << (N - 1 - i));
      }
      if (s[i] == '0') {
        cntZ++;
        maskZ |= (1 << (N - 1 - i));
      }
      if (s[i] == '?') {
        cntQ++;
        maskQ |= (1 << (N - 1 - i));
      }
    }
    int mn = std::min({cntO, cntZ, cntQ}), ans = 0;
    if (cntQ == mn) {
      ans = val[maskO];
      for (int submask = maskQ; submask > 0; submask = (submask - 1) & maskQ) {
        ans += val[submask | maskO];
      }
    } else if (cntO == mn) {
      for (int submask = maskO; submask > 0; submask = (submask - 1) & maskO) {
        if ((__builtin_popcount(submask) + __builtin_popcount(maskO)) & 1)
          ans -= sos_sub[submask | maskQ];
        else
          ans += sos_sub[submask | maskQ];
      }
      if (__builtin_popcount(maskO) & 1)
        ans -= sos_sub[maskQ];
      else
        ans += sos_sub[maskQ];
    } else {
      ans = sos_super[maskO];
      for (int submask = maskZ; submask > 0; submask = (submask - 1) & maskZ) {
        if (__builtin_popcount(submask) & 1)
          ans -= sos_super[submask | maskO];
        else
          ans += sos_super[submask | maskO];
      }
    }
    std::cout << ans << '\n';
  }
}


int main() {
  // std::freopen("input.txt", "r", stdin);
  // std::freopen("i.inp", "r", stdin);
  // std::freopen("sushi.out", "w", stdout);

  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  clock_t start = clock();

  int tc = 1;
  // std::cin >> tc;
  for (int i = 1; i <= tc; ++i) {
    solve(i);
  }

  std::cerr << "Time elapsed: " << clock() - start << " ms\n";
}

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