제출 #41149

#제출 시각아이디문제언어결과실행 시간메모리
41149kriiiSnake Escaping (JOI18_snake_escaping)C++14
100 / 100
1012 ms21820 KiB
#include <stdio.h> #include <algorithm> using namespace std; int L,Q; char sc[1<<20+2]; int bc[1<<20]; int Z[1<<20],O[1<<20]; void go(int l, int r) { if (l+1 == r) return; int m = (l + r) / 2; go(l,m); go(m,r); for (int i=l;i<m;i++){ Z[i-l+m] += Z[i]; O[i] += O[i-l+m]; } } int main() { scanf ("%d %d",&L,&Q); scanf ("%s",sc); for (int i=0;i<(1<<L);i++){ if (i) bc[i] = bc[i-(i&(-i))] + 1; Z[i] = O[i] = sc[i] - '0'; } go(0,(1<<L)); while (Q--){ char q[22]; scanf ("%s",q); int z = 0, o = 0, f = 0; for (int i=0;i<L;i++){ if (q[i] == '0') z |= 1 << (L - i - 1); if (q[i] == '1') o |= 1 << (L - i - 1); if (q[i] == '?') f |= 1 << (L - i - 1); } int m = min({bc[z],bc[o],bc[f]}); int ans = 0; if (bc[f] == m){ for (int x=f;;x=(x-1)&f){ ans += sc[x|o] - '0'; if (!x) break; } } else if (bc[o] == m){ for (int x=o;;x=(x-1)&o){ int b = f + x; if (bc[o] % 2 != bc[x] % 2) ans -= Z[b]; else ans += Z[b]; if (!x) break; } } else{ for (int x=z;;x=(x-1)&z){ int b = o + z - x; if (bc[z] % 2 != bc[x] % 2) ans -= O[b]; else ans += O[b]; if (!x) break; } } printf ("%d\n",ans); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp:6:10: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 char sc[1<<20+2]; int bc[1<<20];
          ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:24:23: 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:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%s",sc);
                 ^
snake_escaping.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char q[22]; scanf ("%s",q);
                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...