oj.uz

Submission #197288

# Submission time Handle Problem Language Result Execution time Memory
197288 2020-01-20T07:02:10 Z dennisstar Snake Escaping (JOI18_snake_escaping) C++11
12 / 100
 2000 ms 20316 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 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^(1<<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^(1<<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^(1<<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);
	for (int i=0; i<(1<<L); i++) scanf("%1d", &a1[i]);
	for (int i=0; i<(1<<L); i++) {
		bs.clear();
		int 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]+=a1[i];
	}
	for (int i=0; i<(1<<L); i++) {
		bs.clear();
		int 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++) a3[stk[j].fi]+=a1[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;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:68: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:69: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", &a1[i]);
                               ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:96: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 3 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 9 ms 352 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 9 ms 352 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 495 ms 4584 KB Output is correct
12 Correct 572 ms 14968 KB Output is correct
13 Correct 480 ms 14072 KB Output is correct
14 Correct 472 ms 14124 KB Output is correct
15 Correct 461 ms 15228 KB Output is correct
16 Correct 507 ms 14444 KB Output is correct
17 Correct 553 ms 14456 KB Output is correct
18 Correct 272 ms 16120 KB Output is correct
19 Correct 291 ms 13176 KB Output is correct
20 Correct 653 ms 14968 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 9 ms 352 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 495 ms 4584 KB Output is correct
12 Correct 572 ms 14968 KB Output is correct
13 Correct 480 ms 14072 KB Output is correct
14 Correct 472 ms 14124 KB Output is correct
15 Correct 461 ms 15228 KB Output is correct
16 Correct 507 ms 14444 KB Output is correct
17 Correct 553 ms 14456 KB Output is correct
18 Correct 272 ms 16120 KB Output is correct
19 Correct 291 ms 13176 KB Output is correct
20 Correct 653 ms 14968 KB Output is correct
21 Correct 760 ms 18476 KB Output is correct
22 Correct 1004 ms 18584 KB Output is correct
23 Correct 653 ms 17492 KB Output is correct
24 Correct 645 ms 17404 KB Output is correct
25 Correct 575 ms 19524 KB Output is correct
26 Correct 648 ms 17916 KB Output is correct
27 Correct 751 ms 17756 KB Output is correct
28 Correct 318 ms 20316 KB Output is correct
29 Correct 434 ms 16204 KB Output is correct
30 Correct 1164 ms 18620 KB Output is correct
31 Correct 670 ms 18424 KB Output is correct
32 Correct 641 ms 18472 KB Output is correct
33 Correct 910 ms 17252 KB Output is correct
34 Correct 808 ms 17400 KB Output is correct
35 Correct 753 ms 17896 KB Output is correct
36 Execution timed out 2060 ms 2416 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 9 ms 352 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 495 ms 4584 KB Output is correct
12 Correct 572 ms 14968 KB Output is correct
13 Correct 480 ms 14072 KB Output is correct
14 Correct 472 ms 14124 KB Output is correct
15 Correct 461 ms 15228 KB Output is correct
16 Correct 507 ms 14444 KB Output is correct
17 Correct 553 ms 14456 KB Output is correct
18 Correct 272 ms 16120 KB Output is correct
19 Correct 291 ms 13176 KB Output is correct
20 Correct 653 ms 14968 KB Output is correct
21 Correct 760 ms 18476 KB Output is correct
22 Correct 1004 ms 18584 KB Output is correct
23 Correct 653 ms 17492 KB Output is correct
24 Correct 645 ms 17404 KB Output is correct
25 Correct 575 ms 19524 KB Output is correct
26 Correct 648 ms 17916 KB Output is correct
27 Correct 751 ms 17756 KB Output is correct
28 Correct 318 ms 20316 KB Output is correct
29 Correct 434 ms 16204 KB Output is correct
30 Correct 1164 ms 18620 KB Output is correct
31 Correct 670 ms 18424 KB Output is correct
32 Correct 641 ms 18472 KB Output is correct
33 Correct 910 ms 17252 KB Output is correct
34 Correct 808 ms 17400 KB Output is correct
35 Correct 753 ms 17896 KB Output is correct
36 Execution timed out 2060 ms 2416 KB Time limit exceeded
37 Halted 0 ms 0 KB -