oj.uz

Submission #252182

# Submission time Handle Problem Language Result Execution time Memory
252182 2020-07-24T15:22:59 Z Nightlight Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 2 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() {
  scanf("%d %d", &L, &Q);
  for(int i = 0; i < (1 << L); i++) {
    scanf(" %c", &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 << "-> " << dp1[(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--) {
      scanf(" %c", &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]);
    }
  }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &L, &Q);
   ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %c", &ch);
     ~~~~~^~~~~~~~~~~~
snake_escaping.cpp:32:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &ch);
       ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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 2 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 2 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 2 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 -