제출 #197281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197281		dennisstar	Snake Escaping (JOI18_snake_escaping)	C++11	5 / 100	2048 ms	12588 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)];
int a1[(1<<20)], a2[(1<<20)], a3[(1<<20)]; //01, 0?, ?1
char s[20];

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);
	for (int i=0; i<L; i++) if (s[i]=='?') cnt++;
	for (int i=0; i<(1<<cnt); i++) {
		int y=x;
		for (int j=0, k=0; j<L; j++) if (s[j]=='?') {
			if ((1<<k)&i) y^=(1<<j);
			k++;
		}
		ans+=a1[y];
	}
	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);
	for (int i=0; i<L; i++) if (s[i]=='1') cnt++;
	for (int i=0; i<(1<<cnt); i++) {
		int y=x;
		for (int j=0, k=0; j<L; j++) if (s[j]=='1') {
			if ((1<<k)&i) y^=(1<<j);
			k++;
		}
		ans+=a2[y]*(__builtin_popcount(i)%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);
	for (int i=0; i<L; i++) if (s[i]=='0') cnt++;
	for (int i=0; i<(1<<cnt); i++) {
		int y=x;
		for (int j=0, k=0; j<L; j++) if (s[j]=='0') {
			if ((1<<k)&i) y^=(1<<j);
			k++;
		}
		ans+=a3[y]*(__builtin_popcount(i)%2?-1:1);
	}
	printf("%d\n", ans);
}

int main() {
	scanf("%d %d", &L, &Q);
	for (int i=0; i<(1<<L); i++) scanf("%1d", &ar[i]);
	for (int i=0; i<(1<<L); i++) a1[i]=ar[i];
	for (int i=0; i<(1<<L); i++) {
		int im, cnt=0;
		for (int j=0; j<L; j++) if (!(i&(1<<j))) cnt++;
		for (int j=0; j<(1<<cnt); j++) {
			im=i;
			for (int k=0, l=0; k<L; k++) {
				if (!(i&(1<<k))) {
					if ((1<<l)&j) im^=(1<<k);
					l++;
				}
			}
			a2[im]+=ar[i];
		}
	}
	for (int i=0; i<(1<<L); i++) {
		int im, cnt=0;
		for (int j=0; j<L; j++) if (i&(1<<j)) cnt++;
		for (int j=0; j<(1<<cnt); j++) {
			im=i;
			for (int k=0, l=0; k<L; k++) {
				if (i&(1<<k)) {
					if ((1<<l)&j) im^=(1<<k);
					l++;
				}
			}
			a3[im]+=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);
		cq<=6?f1():c1<=6?f2():f3();
	}
	return 0;
}

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

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:67: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:68:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0; i<(1<<L); i++) scanf("%1d", &ar[i]);
                               ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

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