oj.uz

Submission #964798

# Submission time Handle Problem Language Result Execution time Memory
964798 2024-04-17T15:03:21 Z Baytoro Snake Escaping (JOI18_snake_escaping) C++17
65 / 100
 2000 ms 16136 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],dp2[N],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]=dp2[i]=a[i];
	for(int i=0;i<n;i++){
		for(int mask=0;mask<(1<<n);mask++){
			if(mask&(1<<i)) dp[mask]+=dp[mask^(1<<i)];
			else dp2[mask]+=dp2[mask^(1<<i)];
		}
	}
	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];
				else ans+=dp[tmpsum];
			}
		}
		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-=dp2[tmpsum];
				else ans+=dp2[tmpsum];
			}
		}
		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 3 ms 4696 KB Output is correct
2 Correct 3 ms 4448 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4448 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1639 ms 13992 KB Output is correct
12 Correct 1653 ms 13832 KB Output is correct
13 Correct 1474 ms 13092 KB Output is correct
14 Correct 1454 ms 13156 KB Output is correct
15 Correct 1924 ms 14048 KB Output is correct
16 Correct 1536 ms 13244 KB Output is correct
17 Correct 1514 ms 13164 KB Output is correct
18 Correct 1262 ms 15144 KB Output is correct
19 Correct 1351 ms 12104 KB Output is correct
20 Correct 1670 ms 13648 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4448 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1639 ms 13992 KB Output is correct
12 Correct 1653 ms 13832 KB Output is correct
13 Correct 1474 ms 13092 KB Output is correct
14 Correct 1454 ms 13156 KB Output is correct
15 Correct 1924 ms 14048 KB Output is correct
16 Correct 1536 ms 13244 KB Output is correct
17 Correct 1514 ms 13164 KB Output is correct
18 Correct 1262 ms 15144 KB Output is correct
19 Correct 1351 ms 12104 KB Output is correct
20 Correct 1670 ms 13648 KB Output is correct
21 Execution timed out 2044 ms 16136 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4448 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 114 ms 15348 KB Output is correct
12 Correct 96 ms 15340 KB Output is correct
13 Correct 120 ms 15336 KB Output is correct
14 Correct 130 ms 15384 KB Output is correct
15 Correct 106 ms 15344 KB Output is correct
16 Correct 144 ms 15336 KB Output is correct
17 Correct 166 ms 15348 KB Output is correct
18 Correct 88 ms 15384 KB Output is correct
19 Correct 107 ms 15232 KB Output is correct
20 Correct 110 ms 15200 KB Output is correct
21 Correct 113 ms 15356 KB Output is correct
22 Correct 130 ms 15344 KB Output is correct
23 Correct 122 ms 15264 KB Output is correct
24 Correct 154 ms 15632 KB Output is correct
25 Correct 134 ms 15448 KB Output is correct
26 Correct 91 ms 15284 KB Output is correct
27 Correct 114 ms 15256 KB Output is correct
28 Correct 106 ms 15188 KB Output is correct
29 Correct 135 ms 15340 KB Output is correct
30 Correct 141 ms 15368 KB Output is correct
31 Correct 104 ms 15340 KB Output is correct
32 Correct 151 ms 15380 KB Output is correct
33 Correct 124 ms 15252 KB Output is correct
34 Correct 92 ms 15436 KB Output is correct
35 Correct 140 ms 15348 KB Output is correct
36 Correct 145 ms 15476 KB Output is correct
37 Correct 131 ms 15244 KB Output is correct
38 Correct 146 ms 15560 KB Output is correct
39 Correct 148 ms 15344 KB Output is correct
40 Correct 125 ms 15176 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4448 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1639 ms 13992 KB Output is correct
12 Correct 1653 ms 13832 KB Output is correct
13 Correct 1474 ms 13092 KB Output is correct
14 Correct 1454 ms 13156 KB Output is correct
15 Correct 1924 ms 14048 KB Output is correct
16 Correct 1536 ms 13244 KB Output is correct
17 Correct 1514 ms 13164 KB Output is correct
18 Correct 1262 ms 15144 KB Output is correct
19 Correct 1351 ms 12104 KB Output is correct
20 Correct 1670 ms 13648 KB Output is correct
21 Execution timed out 2044 ms 16136 KB Time limit exceeded
22 Halted 0 ms 0 KB -