oj.uz

Submission #964781

# Submission time Handle Problem Language Result Execution time Memory
964781 2024-04-17T14:21:50 Z Baytoro Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 53948 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=1e6+5;
int dp[(1<<20)][2];
void solve(){
	int n,q;cin>>n>>q;
	string s;cin>>s;
	vector<int> a((1<<n));
	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<s.size();i++){
			if(st[i]=='?') u++;
			else if(st[i]=='0') z++;
			else o++;
		}
		int sum=0,ans=0;
		vector<int> tmp;
		if(u<=z && u<=o){
			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<=z && o<=u){
			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) c=-1;
				else c=1;
				ans+=c*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) c=-1;
				else c=1;
				ans+=c*dp[tmpsum][1];
			}
		}
		cout<<ans<<endl;
	}
}
signed main(){
	int t=1;//cin>>t;
	while(t--)
	solve();
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Execution timed out 2033 ms 13276 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Execution timed out 2033 ms 13276 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Runtime error 67 ms 53948 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Execution timed out 2033 ms 13276 KB Time limit exceeded
12 Halted 0 ms 0 KB -