제출 #500549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500549		codr0	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1715 ms	65536 KiB

snake_escaping

#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int Q=1e6+4;
const int N=1050000;
int ans[Q];
int A[N];
char qu[Q][21];
int l,q;
int n;
int pw[21];
int Lg[N];
int F[N];

	void solve(){
		FOR(i,0,n-1) F[i]=A[i];
		FOR(i,0,l-1) FOR(msk,0,n-1)
		if(msk&pw[i])	F[msk]+=F[msk^pw[i]];
		int dp0[N];
		FOR(i,0,n-1) dp0[i]=F[i^(n-1)];
		FOR(i,0,q-1) if(ans[i]==-1){
			int tq(0),t[2]={};
			FOR(j,0,l-1) if(qu[i][j]=='?') tq++; else t[qu[i][j]-'0']++;
			if(tq<=7){
				ans[i]=0;
				vector<int> qq;
				int K=0;
				FOR(j,0,l-1) if(qu[i][j]=='?') qq.pb(j); else if(qu[i][j]=='1') K+=pw[j];
				FOR(j,0,pw[tq]-1){
					int J=j;
					int k=K;
					while(J){
						k+=pw[qq[Lg[(J&(-J))]]];
						J-=(J&(-J));
					}
					ans[i]+=A[k];
				}
			}else if(t[0]>=t[1]){
				ans[i]=0;
				vector<int> qq;
				int K=0;
				FOR(j,0,l-1) if(qu[i][j]=='0') K+=pw[j]; else if(qu[i][j]=='1') qq.pb(j);
				FOR(j,0,pw[t[1]]-1){
					int J=j;
					int k=K;
					int t=0;
					while(J){
						k+=pw[qq[Lg[(J&(-J))]]];
						t++;
						J-=(J&(-J));
					}
					if(t&1) ans[i]-=dp0[k];
					else ans[i]+=dp0[k];
				}
			}
		}
	}

	int32_t main() {
	/*ios_base::sync_with_stdio(0);*/ cin.tie(0);
	
	pw[0]=1; FOR(i,1,20) pw[i]=2*pw[i-1];
	FOR(i,0,20) Lg[pw[i]]=i;
	cin>>l>>q;
	n=pw[l];
	FOR(i,0,q) ans[i]=-1;
	//string s0; cin>>s0;
	getchar();
	FOR(i,0,n-1) A[i]=getchar()-'0'; getchar();
	FOR(i,0,q-1){
		//string x0; cin>>x0; qu.pb(x0);
		FOR(j,0,l-1) qu[i][j]=getchar();
		FOR(j,0,l-1){
			if(((l-1)-j)<=j) break;
			swap(qu[i][j],qu[i][((l-1)-j)]);
		}
		getchar();
	}
	solve();
	FOR(i,0,n-1){
		if((i^(n-1))<=i) break;
		swap(A[i],A[(i^(n-1))]);
	}
	FOR(i,0,q-1){
		FOR(j,0,l-1) if(qu[i][j]!='?') qu[i][j]=((1-(qu[i][j]-'0'))+'0');
	}
	solve();
	FOR(i,0,q-1) cout<<ans[i]<<'\n';

	return 0;
    }

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

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:4:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    4 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
      |                    ^~~
snake_escaping.cpp:79:2: note: in expansion of macro 'FOR'
   79 |  FOR(i,0,n-1) A[i]=getchar()-'0'; getchar();
      |  ^~~
snake_escaping.cpp:79:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |  FOR(i,0,n-1) A[i]=getchar()-'0'; getchar();
      |                                   ^~~~~~~

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