Submission #952731

#	Time	Username	Problem	Language	Result	Execution time	Memory
952731		wojciech_domin2	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2066 ms	39388 KiB

snake_escaping

#include <bits/stdc++.h>
#define pb push_back
#define ins insert
#define fi first
#define se second
#define debug(x) cout<<#x<<" = "<<x<<"\n"; 

using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.fi<<", "<<m.se<<")";
}
 
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}

const int MAX_Q = 1000500;
const int MAX_N = (1<<20)+50;
bitset<64> s[MAX_Q];
int odp[MAX_Q];
int L, Q;

void rekur(vector<int> &v, vector<int> &zapyt, int k){
	if(zapyt.size()==0) {
		v.clear();
		v.shrink_to_fit();
		zapyt.clear();
		zapyt.shrink_to_fit();
		return;
	}
	if(v.size() == 0) return;
	if(v.size() == 1){
		for(auto x : zapyt) odp[x] = v[0];
		v.clear();
		v.shrink_to_fit();
		zapyt.clear();
		zapyt.shrink_to_fit();
		return;
	}
	vector<int> v1,v2,v3;
	for(int i = 0; i < v.size()/2; i++){
		v1.pb(v[i]);
		v2.pb(v[i+v.size()/2]);
		v3.pb(v[i]+v[i+v.size()/2]);
	}
	v.clear();
	v.shrink_to_fit();
	vector<int> z1,z2,z3;
	for(int i = 0; i < zapyt.size(); i++){
		if(!s[zapyt[i]][2*k] && !s[zapyt[i]][2*k+1]) z1.pb(zapyt[i]);
		if(s[zapyt[i]][2*k]) z2.pb(zapyt[i]);
		if(s[zapyt[i]][2*k+1]) z3.pb(zapyt[i]);
	}
	zapyt.clear();
	zapyt.shrink_to_fit();
	rekur(v1,z1,k+1);
	rekur(v2,z2,k+1);
	rekur(v3,z3,k+1);
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	ll maxt = -1;
	cin>>L>>Q;
	vector<int> pom,zap;
	for(int i = 0; i < (1<<L); i++){
		char c; cin >> c; pom.pb(int(c-'0'));
	}
	for(int i = 1; i <= Q; i++){
		for(int j = 0; j < L; j++){
			char c; cin>>c;
			if(c == '0'){
				s[i][2*j] = 0; 
			}
			if(c == '1'){
				s[i][2*j] = 1;
			}
			if(c == '?'){
				s[i][2*j+1] = 1;
			}
		}
	}
	for(int i = 1; i <= Q; i++) zap.pb(i);
	rekur(pom,zap,0);
	for(int i = 1; i <= Q; i++) cout<<odp[i]<<"\n";
	





}

Compilation message (stderr)

snake_escaping.cpp: In function 'void rekur(std::vector<int>&, std::vector<int>&, int)':
snake_escaping.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < v.size()/2; i++){
      |                 ~~^~~~~~~~~~~~
snake_escaping.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < zapyt.size(); i++){
      |                 ~~^~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:78:5: warning: unused variable 'maxt' [-Wunused-variable]
   78 |  ll maxt = -1;
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25