Submission #881482

#	Time	Username	Problem	Language	Result	Execution time	Memory
881482		mgl_diamond	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	618 ms	39308 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

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

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 20;

int n, q, full;
char a[1<<20];
int sum[1<<20], rsum[1<<20];

int main() {
  setIO();

  cin >> n >> q;
  full = (1<<n)-1;
  foru(i, 0, full) cin >> a[i];
  foru(i, 0, full) {
    a[i] -= '0';
    sum[i] = a[i];
    rsum[i] = a[i];
  }

  foru(bt, 0, n-1) {
    foru(i, 0, full) {
      if (i >> bt & 1)
        sum[i] += sum[i-(1<<bt)];
      else
        rsum[i] += rsum[i+(1<<bt)];
    }
  }

  int cap = n/3;
  while (q--) {
    string s;
    cin >> s;
    reverse(all(s));

    int cnt[3] = {}, ans = 0;
    foru(i, 0, n-1) {
      if (s[i] == '?') cnt[0] += 1;
      else if (s[i] == '1') cnt[1] += 1;
      else cnt[2] += 1;
    }

    if (cnt[0] <= cap) {
      int num = 0, mask = 0;
      foru(i, 0, n-1) 
        if (s[i] == '?') mask += 1 << i;
        else if (s[i] == '1') num += 1 << i;
      for(int i=mask; ; i=(i-1)&mask) {
        ans += a[i|num];
        if (i == 0) break;
      }
      cout << ans << "\n";
    }
    else if (cnt[1] <= cap) {
      int num = 0, mask = 0;
      foru(i, 0, n-1) 
        if (s[i] == '?') num += 1 << i;
        else if (s[i] == '1') mask += 1 << i;
      for(int i=mask; ; i=(i-1)&mask) {
        if ((cnt[1]-__builtin_popcount(i)) & 1) ans -= sum[num|i];
        else ans += sum[num|i];
        if (i == 0) break;
      }
      cout << ans << "\n";
    }
    else {
      int num = 0, mask = 0;
      foru(i, 0, n-1) 
        if (s[i] == '1') num += 1 << i;
        else if (s[i] == '0') mask += 1 << i;
      for(int i = mask; ; i=(i-1)&mask) {
        if (__builtin_popcount(i) & 1) ans -= rsum[num|i];
        else ans += rsum[num|i];
        if (i == 0) break;
      }
      cout << ans << "\n";
    }
  }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void setIO()':
snake_escaping.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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