제출 #66814

#제출 시각아이디문제언어결과실행 시간메모리
66814hamzqq9Snake Escaping (JOI18_snake_escaping)C++14
12 / 100
2084 ms43776 KiB
#include<bits/stdc++.h> #define st first #define nd second #define pb push_back #define ppb pop_back #define umax(x,y) x=max(x,y) #define umin(x,y) x=min(x,y) #define ll long long #define ii pair<int,int> #define iii pair<int,ii> #define sz(x) ((int) x.size()) #define orta ((bas+son)>>1) #define all(x) x.begin(),x.end() #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define pw(x) (1<<(x)) #define inf 100000000000000 #define MOD 1000000007 #define N 100005 #define MAX 10000006 #define L 13 #define R 7 #define LOG 22 using namespace std; unsigned short int ans[pw(L)][2189]; char val[pw(20)+3]; short int po3[12]; int l,q,n; int res; short int value; char s[pw(20)+3]; int po2[27]; int sz; pair<char,short int> stck[pw(L)+5]; int get_pos_of_2(int value) { int cur=0; while(value) { if(value%3==2) return cur; value/=3; cur++; } return -1; } int get_val(int bas,int son) { int cur=0; for(int i=bas;i<=son;i++) { cur+=po3[son-i]*(s[i]=='?'?2:(s[i]-'0')); } return cur; } int get_2_rep(int val) { int res=0; int curpw=1; while(val) { res+=curpw*(val%3); curpw*=2; val/=3; } return res; } void back_track(char bit,short int val) { stck[sz++]={bit,val}; while(sz) { sz--; char bit=stck[sz].st; short int val=stck[sz].nd; if(bit==-1) { res+=ans[val][value]; continue ; } if(s[bit]!='?') { stck[sz++]={bit-1,val+po2[L-1-bit]*(s[bit]=='1')}; } else { stck[sz++]={bit-1,val+po2[L-1-bit]}; stck[sz++]={bit-1,val}; } } } void pre_calc() { for(int i=0;i<po3[R];i++) { char pos=get_pos_of_2(i); short int temp=-1; if(pos==-1) temp=get_2_rep(i); for(int j=0;j<po2[L];j++) { if(pos==-1) { ans[j][i]=val[temp+po2[R]*j]; } else { ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2]; } } } } int main() { // freopen("input.txt","r",stdin); scanf("%d %d",&l,&q); po3[0]=1; for(int i=1;i<=10;i++) po3[i]=po3[i-1]*3; for(int i=0;i<25;i++) po2[i]=pw(i); n=po2[l]; scanf("%s",s); for(int i=0;i<n;i++) { val[i]=s[i]-'0'; } pre_calc(); while(q--) { scanf("%s",s+20-l); for(int i=0;i<20-l;i++) s[i]='0'; res=0; value=get_val(L,19); back_track(L-1,0); printf("%d\n",res); } }

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

snake_escaping.cpp: In function 'void back_track(char, short int)':
snake_escaping.cpp:108:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(s[bit]!='?') {
           ^
snake_escaping.cpp:110:45: warning: array subscript has type 'char' [-Wchar-subscripts]
    stck[sz++]={bit-1,val+po2[L-1-bit]*(s[bit]=='1')};
                                             ^
snake_escaping.cpp: In function 'void pre_calc()':
snake_escaping.cpp:142:31: warning: array subscript has type 'char' [-Wchar-subscripts]
     ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];
                               ^
snake_escaping.cpp:142:50: warning: array subscript has type 'char' [-Wchar-subscripts]
     ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];
                                                  ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:156:7: 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:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s+20-l);
   ~~~~~^~~~~~~~~~~~~
#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...