제출 #197285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197285		dennisstar	Snake Escaping (JOI18_snake_escaping)	C++11	0 / 100	10 ms	604 KiB

snake_escaping

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int L, Q;
int ar[(1<<20)]; char AR[(1<<20)];
int a1[(1<<20)], a2[(1<<20)], a3[(1<<20)]; //01, 0?, ?1
char s[20];
pii stk[(1<<20)];
vim bs;

inline void f1() { //a1
	int cnt=0, x=0, ans=0;
	for (int i=0; i<L; i++) if (s[i]=='1') x|=(1<<i);
	bs.clear();
	for (int i=0; i<L; i++) if (s[i]=='?') { cnt++; bs.eb(i); }
	stk[0]=pii(x, 0);
	int tp=1, e=1;
	for (int i=0; i<cnt; i++) {
		for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], 0);
		e=tp;
	}
	for (int i=0; i<e; i++) ans+=a1[stk[i].fi];
	printf("%d\n", ans);
}
inline void f2() { //a2
	int cnt=0, x=0, ans=0;
	for (int i=0; i<L; i++) if (s[i]=='?'||s[i]=='1') x|=(1<<i);
	bs.clear();
	for (int i=0; i<L; i++) if (s[i]=='1') { cnt++; bs.eb(i); }
	stk[0]=pii(x, 0);
	int tp=1, e=1;
	for (int i=0; i<cnt; i++) {
		for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], stk[j].se+1);
		e=tp;
	}
	for (int i=0; i<e; i++) ans+=a2[stk[i].fi]*(stk[i].se%2?-1:1);
	printf("%d\n", ans);
}
inline void f3() { //a3
	int cnt=0, x=0, ans=0;
	for (int i=0; i<L; i++) if (s[i]=='1') x|=(1<<i);
	bs.clear();
	for (int i=0; i<L; i++) if (s[i]=='0') { cnt++; bs.eb(i); }
	stk[0]=pii(x, 0);
	int tp=1, e=1;
	for (int i=0; i<cnt; i++) {
		for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], stk[j].se+1);
		e=tp;
	}
	for (int i=0; i<e; i++) ans+=a3[stk[i].fi]*(stk[i].se%2?-1:1);
	printf("%d\n", ans);
}

int main() {
	scanf("%d %d", &L, &Q);
	scanf("%s", AR);
	for (int i=0; i<(1<<L); i++) ar[i]=AR[i]-'0';
	for (int i=0; i<(1<<L); i++) a1[i]=ar[i];
	for (int i=0; i<(1<<L); i++) {
		bs.clear();
		int im, cnt=0;
		for (int j=0; j<L; j++) if (!(i&(1<<j))) {
			cnt++;
			bs.eb(j);
		}
		int e=1, tp=1;
		stk[0]=pii(i, 0);
		for (int j=0; j<cnt; j++) {
			for (int k=0; k<e; k++) stk[tp++]=pii(stk[k].fi^(1<<bs[j]), 0);
			e=tp;
		}
		for (int j=0; j<e; j++) a2[stk[j].fi]+=ar[i];
	}
	for (int i=0; i<(1<<L); i++) {
		bs.clear();
		int im, cnt=0;
		for (int j=0; j<L; j++) if (i&(1<<j)) {
			cnt++;
			bs.eb(j);
		}
		int e, tp=1;
		stk[0]=pii(i, 0);
		for (int j=0; j<cnt; j++) {
			for (int k=0; k<e; k++) stk[tp++]=pii(stk[k].fi^(1<<bs[j]), 0);
			e=tp;
		}
		for (int j=0; j<e; j++) a3[stk[j].fi]+=ar[i];
	}

	while (Q--) {
		scanf("%s", s);
		int c0=0, c1=0, cq=0;
		for (int i=0; i<L; i++) (s[i]=='0'?c0:s[i]=='1'?c1:cq)++;
		reverse(s, s+L);
		if (c0<=c1&&c0<=cq) f2();
		else if (c1<=c0&&c1<=cq) f3();
		else f1();
	}
	return 0;
}

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

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:7: warning: unused variable 'im' [-Wunused-variable]
   int im, cnt=0;
       ^~
snake_escaping.cpp:90:7: warning: unused variable 'im' [-Wunused-variable]
   int im, cnt=0;
       ^~
snake_escaping.cpp:69: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:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", AR);
  ~~~~~^~~~~~~~~~
snake_escaping.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
snake_escaping.cpp:95:7: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int e, tp=1;
       ^

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