oj.uz

Submission #964797

# Submission time Handle Problem Language Result Execution time Memory
964797 2024-04-17T15:00:55 Z Baytoro Snake Escaping (JOI18_snake_escaping) C++17
65 / 100
 2000 ms 18664 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
//#define mp make_pair
#define ll long long
//#define int ll
//#define double long double
const ll INF=1e18,N=(1<<20)+5;
int dp[N][2],a[N];
void solve(){
	int n,q;cin>>n>>q;
	string s;cin>>s;
	for(int i=0;i<(1<<n);i++) a[i]=(s[i]-'0');
	for(int i=0;i<(1<<n);i++) dp[i][0]=dp[i][1]=a[i];
	for(int i=0;i<n;i++){
		for(int mask=0;mask<(1<<n);mask++){
			if(mask&(1<<i)) dp[mask][0]+=dp[mask^(1<<i)][0];
			else dp[mask][1]+=dp[mask^(1<<i)][1];
		}
	}
	while(q--){
		string st;cin>>st;reverse(all(st));
		int z=0,o=0,u=0;
		for(int i=0;i<st.size();i++){
			if(st[i]=='?') u++;
			else if(st[i]=='0') z++;
			else o++;
		}
		int sum=0,ans=0;
		vector<int> tmp;
		if(u<=6){
			for(int i=0;i<n;i++){
				if(st[i]=='1') sum+=(1<<i);
				if(st[i]=='?') tmp.pb(1<<i);
			}
			for(int i=0;i<(1<<tmp.size());i++){
				int tmpsum=sum;
				for(int j=0;j<tmp.size();j++){
					if(i&(1<<j)) tmpsum+=tmp[j];
				}
				ans+=a[tmpsum];
			}
		}
		else if(o<=6){
			for(int i=0;i<n;i++){
				if(st[i]=='1' || st[i]=='?') sum+=(1<<i);
				if(st[i]=='1') tmp.pb(1<<i);
			}
			for(int i=0;i<(1<<tmp.size());i++){
				int tmpsum=sum,c=0;
				for(int j=0;j<tmp.size();j++){
					if(i&(1<<j)){
						tmpsum^=(tmp[j]);
						c++;
					}
				}
				if(c%2) ans-=dp[tmpsum][0];
				else ans+=dp[tmpsum][0];
			}
		}
		else{
			for(int i=0;i<n;i++){
				if(st[i]=='1') sum+=(1<<i);
				if(st[i]=='0') tmp.pb(1<<i);
			}
			for(int i=0;i<(1<<tmp.size());i++){
				int tmpsum=sum,c=0;
				for(int j=0;j<tmp.size();j++){
					if(!(i&(1<<j))){
						tmpsum^=(tmp[j]);
						c++;
					}
				}
				if(c%2) ans-=dp[tmpsum][1];
				else ans+=dp[tmpsum][1];
			}
		}
		cout<<ans<<endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;//cin>>t;
	while(t--)
	solve();
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<st.size();i++){
      |               ~^~~~~~~~~~
snake_escaping.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
snake_escaping.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
snake_escaping.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1622 ms 17224 KB Output is correct
12 Correct 1585 ms 16924 KB Output is correct
13 Correct 1456 ms 16076 KB Output is correct
14 Correct 1491 ms 16108 KB Output is correct
15 Correct 1976 ms 17092 KB Output is correct
16 Correct 1550 ms 16392 KB Output is correct
17 Correct 1522 ms 16400 KB Output is correct
18 Correct 1282 ms 18056 KB Output is correct
19 Correct 1303 ms 15280 KB Output is correct
20 Correct 1641 ms 16884 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1622 ms 17224 KB Output is correct
12 Correct 1585 ms 16924 KB Output is correct
13 Correct 1456 ms 16076 KB Output is correct
14 Correct 1491 ms 16108 KB Output is correct
15 Correct 1976 ms 17092 KB Output is correct
16 Correct 1550 ms 16392 KB Output is correct
17 Correct 1522 ms 16400 KB Output is correct
18 Correct 1282 ms 18056 KB Output is correct
19 Correct 1303 ms 15280 KB Output is correct
20 Correct 1641 ms 16884 KB Output is correct
21 Execution timed out 2005 ms 18664 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 103 ms 16116 KB Output is correct
12 Correct 107 ms 16108 KB Output is correct
13 Correct 118 ms 16244 KB Output is correct
14 Correct 142 ms 16112 KB Output is correct
15 Correct 108 ms 16020 KB Output is correct
16 Correct 169 ms 16016 KB Output is correct
17 Correct 152 ms 16164 KB Output is correct
18 Correct 87 ms 16208 KB Output is correct
19 Correct 106 ms 15860 KB Output is correct
20 Correct 101 ms 16028 KB Output is correct
21 Correct 117 ms 15984 KB Output is correct
22 Correct 138 ms 16096 KB Output is correct
23 Correct 116 ms 15988 KB Output is correct
24 Correct 127 ms 16112 KB Output is correct
25 Correct 138 ms 16164 KB Output is correct
26 Correct 89 ms 16024 KB Output is correct
27 Correct 105 ms 16428 KB Output is correct
28 Correct 97 ms 15860 KB Output is correct
29 Correct 123 ms 15928 KB Output is correct
30 Correct 142 ms 16060 KB Output is correct
31 Correct 114 ms 16208 KB Output is correct
32 Correct 152 ms 16056 KB Output is correct
33 Correct 130 ms 16116 KB Output is correct
34 Correct 113 ms 15832 KB Output is correct
35 Correct 127 ms 16148 KB Output is correct
36 Correct 124 ms 16108 KB Output is correct
37 Correct 125 ms 16148 KB Output is correct
38 Correct 134 ms 15928 KB Output is correct
39 Correct 131 ms 15976 KB Output is correct
40 Correct 122 ms 16152 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1622 ms 17224 KB Output is correct
12 Correct 1585 ms 16924 KB Output is correct
13 Correct 1456 ms 16076 KB Output is correct
14 Correct 1491 ms 16108 KB Output is correct
15 Correct 1976 ms 17092 KB Output is correct
16 Correct 1550 ms 16392 KB Output is correct
17 Correct 1522 ms 16400 KB Output is correct
18 Correct 1282 ms 18056 KB Output is correct
19 Correct 1303 ms 15280 KB Output is correct
20 Correct 1641 ms 16884 KB Output is correct
21 Execution timed out 2005 ms 18664 KB Time limit exceeded
22 Halted 0 ms 0 KB -