oj.uz

Submission #252188

# Submission time Handle Problem Language Result Execution time Memory
252188 2020-07-24T15:35:34 Z Nightlight Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 1 ms 384 KB 
#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);
        tmp = mask0 & (tmp - 1);
      }
      printf("%d\n", ans + dp0[mask1]);
    }else {
      tmp = mask1;
      while(tmp) {
        bit = (((1 << L) - 1) ^ mask1);
        ans += dp1[maskq | bit] * -(__builtin_popcount(bit) & 1);
        tmp = mask1 & (tmp - 1);
      }
      printf("%d\n", ans + dp1[maskq + mask1]);
    }
  };
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -