oj.uz

Submission #952731

# Submission time Handle Problem Language Result Execution time Memory
952731 2024-03-24T16:24:40 Z wojciech_domin2 Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 39388 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 2 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 2 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 302 ms 26204 KB Output is correct
12 Correct 333 ms 29032 KB Output is correct
13 Correct 363 ms 28272 KB Output is correct
14 Correct 360 ms 26472 KB Output is correct
15 Correct 302 ms 28872 KB Output is correct
16 Correct 376 ms 28104 KB Output is correct
17 Correct 396 ms 29192 KB Output is correct
18 Correct 190 ms 29616 KB Output is correct
19 Correct 321 ms 26056 KB Output is correct
20 Correct 325 ms 28404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 2 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 302 ms 26204 KB Output is correct
12 Correct 333 ms 29032 KB Output is correct
13 Correct 363 ms 28272 KB Output is correct
14 Correct 360 ms 26472 KB Output is correct
15 Correct 302 ms 28872 KB Output is correct
16 Correct 376 ms 28104 KB Output is correct
17 Correct 396 ms 29192 KB Output is correct
18 Correct 190 ms 29616 KB Output is correct
19 Correct 321 ms 26056 KB Output is correct
20 Correct 325 ms 28404 KB Output is correct
21 Correct 375 ms 30604 KB Output is correct
22 Correct 427 ms 30488 KB Output is correct
23 Correct 571 ms 28132 KB Output is correct
24 Correct 514 ms 27776 KB Output is correct
25 Correct 412 ms 30692 KB Output is correct
26 Correct 620 ms 27784 KB Output is correct
27 Correct 667 ms 30500 KB Output is correct
28 Correct 216 ms 33300 KB Output is correct
29 Correct 371 ms 31456 KB Output is correct
30 Correct 420 ms 31240 KB Output is correct
31 Correct 526 ms 31684 KB Output is correct
32 Correct 505 ms 27880 KB Output is correct
33 Correct 416 ms 30176 KB Output is correct
34 Correct 601 ms 27880 KB Output is correct
35 Correct 673 ms 27812 KB Output is correct
36 Correct 215 ms 31240 KB Output is correct
37 Correct 379 ms 31484 KB Output is correct
38 Correct 409 ms 29060 KB Output is correct
39 Correct 539 ms 27900 KB Output is correct
40 Correct 520 ms 29500 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 2 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 123 ms 18624 KB Output is correct
12 Correct 145 ms 19112 KB Output is correct
13 Correct 499 ms 19276 KB Output is correct
14 Correct 586 ms 19272 KB Output is correct
15 Correct 353 ms 19016 KB Output is correct
16 Correct 557 ms 19272 KB Output is correct
17 Correct 577 ms 19280 KB Output is correct
18 Correct 32 ms 18372 KB Output is correct
19 Correct 124 ms 18768 KB Output is correct
20 Correct 139 ms 19000 KB Output is correct
21 Correct 497 ms 18772 KB Output is correct
22 Correct 596 ms 19280 KB Output is correct
23 Correct 388 ms 18860 KB Output is correct
24 Correct 546 ms 19376 KB Output is correct
25 Correct 585 ms 20304 KB Output is correct
26 Correct 36 ms 18364 KB Output is correct
27 Correct 135 ms 19012 KB Output is correct
28 Correct 136 ms 18760 KB Output is correct
29 Correct 483 ms 18760 KB Output is correct
30 Correct 539 ms 19132 KB Output is correct
31 Correct 366 ms 18776 KB Output is correct
32 Correct 545 ms 19288 KB Output is correct
33 Correct 578 ms 19200 KB Output is correct
34 Correct 33 ms 20376 KB Output is correct
35 Correct 500 ms 19380 KB Output is correct
36 Correct 494 ms 20296 KB Output is correct
37 Correct 540 ms 19044 KB Output is correct
38 Correct 539 ms 19272 KB Output is correct
39 Correct 509 ms 20064 KB Output is correct
40 Correct 488 ms 19276 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 2 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 302 ms 26204 KB Output is correct
12 Correct 333 ms 29032 KB Output is correct
13 Correct 363 ms 28272 KB Output is correct
14 Correct 360 ms 26472 KB Output is correct
15 Correct 302 ms 28872 KB Output is correct
16 Correct 376 ms 28104 KB Output is correct
17 Correct 396 ms 29192 KB Output is correct
18 Correct 190 ms 29616 KB Output is correct
19 Correct 321 ms 26056 KB Output is correct
20 Correct 325 ms 28404 KB Output is correct
21 Correct 375 ms 30604 KB Output is correct
22 Correct 427 ms 30488 KB Output is correct
23 Correct 571 ms 28132 KB Output is correct
24 Correct 514 ms 27776 KB Output is correct
25 Correct 412 ms 30692 KB Output is correct
26 Correct 620 ms 27784 KB Output is correct
27 Correct 667 ms 30500 KB Output is correct
28 Correct 216 ms 33300 KB Output is correct
29 Correct 371 ms 31456 KB Output is correct
30 Correct 420 ms 31240 KB Output is correct
31 Correct 526 ms 31684 KB Output is correct
32 Correct 505 ms 27880 KB Output is correct
33 Correct 416 ms 30176 KB Output is correct
34 Correct 601 ms 27880 KB Output is correct
35 Correct 673 ms 27812 KB Output is correct
36 Correct 215 ms 31240 KB Output is correct
37 Correct 379 ms 31484 KB Output is correct
38 Correct 409 ms 29060 KB Output is correct
39 Correct 539 ms 27900 KB Output is correct
40 Correct 520 ms 29500 KB Output is correct
41 Correct 123 ms 18624 KB Output is correct
42 Correct 145 ms 19112 KB Output is correct
43 Correct 499 ms 19276 KB Output is correct
44 Correct 586 ms 19272 KB Output is correct
45 Correct 353 ms 19016 KB Output is correct
46 Correct 557 ms 19272 KB Output is correct
47 Correct 577 ms 19280 KB Output is correct
48 Correct 32 ms 18372 KB Output is correct
49 Correct 124 ms 18768 KB Output is correct
50 Correct 139 ms 19000 KB Output is correct
51 Correct 497 ms 18772 KB Output is correct
52 Correct 596 ms 19280 KB Output is correct
53 Correct 388 ms 18860 KB Output is correct
54 Correct 546 ms 19376 KB Output is correct
55 Correct 585 ms 20304 KB Output is correct
56 Correct 36 ms 18364 KB Output is correct
57 Correct 135 ms 19012 KB Output is correct
58 Correct 136 ms 18760 KB Output is correct
59 Correct 483 ms 18760 KB Output is correct
60 Correct 539 ms 19132 KB Output is correct
61 Correct 366 ms 18776 KB Output is correct
62 Correct 545 ms 19288 KB Output is correct
63 Correct 578 ms 19200 KB Output is correct
64 Correct 33 ms 20376 KB Output is correct
65 Correct 500 ms 19380 KB Output is correct
66 Correct 494 ms 20296 KB Output is correct
67 Correct 540 ms 19044 KB Output is correct
68 Correct 539 ms 19272 KB Output is correct
69 Correct 509 ms 20064 KB Output is correct
70 Correct 488 ms 19276 KB Output is correct
71 Correct 778 ms 37964 KB Output is correct
72 Correct 914 ms 38404 KB Output is correct
73 Execution timed out 2066 ms 39388 KB Time limit exceeded
74 Halted 0 ms 0 KB -