oj.uz

Submission #197280

# Submission time Handle Problem Language Result Execution time Memory
197280 2020-01-20T05:57:38 Z dennisstar Snake Escaping (JOI18_snake_escaping) C++11
5 / 100
 2000 ms 15360 KB 
#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];

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);
}
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);
}
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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 8 ms 452 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 8 ms 452 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Execution timed out 2021 ms 15360 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 8 ms 452 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Execution timed out 2021 ms 15360 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 8 ms 452 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Execution timed out 2044 ms 13940 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 8 ms 452 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Execution timed out 2021 ms 15360 KB Time limit exceeded
12 Halted 0 ms 0 KB -