oj.uz

Submission #521607

# Submission time Handle Problem Language Result Execution time Memory
521607 2022-02-02T14:35:16 Z AdamGS Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 56620 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
string S;
void solve(vector<ll>&V, vector<int>&ans, int l, int r, ll akt) {
	if(!V.size()) return;
	if(l==r) {
		ans[0]=S[l]-'0';
		return;
	}
	int ile1=0, ile2=0, ile3=0;
	rep(i, V.size()) {
		if(V[i]/akt==0) ++ile1;
		else if(V[i]/akt==1) ++ile2;
		else ++ile3;
	}
	vector<ll>zero, jeden;
	int l1=0, l2=0;
	while(l1<ile1 || l2<ile2) {
		if(l1<ile1) {
			if(l2<ile2) {
				if(V[l1]%akt<=V[ile1+l2]%akt) {
					if(!zero.size() || zero.back()!=V[l1]%akt) zero.pb(V[l1]%akt);
					++l1;
				} else {
					if(!zero.size() || zero.back()!=V[ile1+l2]%akt) zero.pb(V[ile1+l2]%akt);
					++l2;
				}
			} else {
				if(!zero.size() || zero.back()!=V[l1]%akt) zero.pb(V[l1]%akt);
				++l1;
			}
		} else {
			if(!zero.size() || zero.back()!=V[ile1+l2]%akt) zero.pb(V[ile1+l2]%akt);
			++l2;
		}
	}
	vector<int>zans(zero.size());
	solve(zero, zans, l, (l+r)/2, akt/3);
	l1=0;
	rep(i, ile1) {
		while(zero[l1]<V[i]%akt) ++l1;
		ans[i]+=zans[l1];
	}
	l1=0;
	rep(i, ile2) {
		while(zero[l1]<V[ile1+i]%akt) ++l1;
		ans[ile1+i]+=zans[l1];
	}
	l1=0; l2=0;
	while(l1<ile1 || l2<ile3) {
		if(l1<ile1) {
			if(l2<ile3) {
				if(V[l1]%akt<=V[ile1+ile2+l2]%akt) {
					if(!jeden.size() || jeden.back()!=V[l1]%akt) jeden.pb(V[l1]%akt);
					++l1;
				} else {
					if(!jeden.size() || jeden.back()!=V[ile1+ile2+l2]%akt) jeden.pb(V[ile1+ile2+l2]%akt);
					++l2;
				}
			} else {
				if(!jeden.size() || jeden.back()!=V[l1]%akt) jeden.pb(V[l1]%akt);
				++l1;
			}
		} else {
			if(!jeden.size() || jeden.back()!=V[ile1+ile2+l2]%akt) jeden.pb(V[ile1+ile2+l2]%akt);
			++l2;
		}
	}
	vector<int>jans(jeden.size());
	solve(jeden, jans, (l+r)/2+1, r, akt/3);
	l1=0;
	rep(i, ile1) {
		while(jeden[l1]<V[i]%akt) ++l1;
		ans[i]+=jans[l1];
	}
	l1=0;
	rep(i, ile3) {
		while(jeden[l1]<V[ile1+ile2+i]%akt) ++l1;
		ans[ile1+ile2+i]+=jans[l1];
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int l, q, n=1;
	cin >> l >> q >> S;
	rep(i, l) n*=2;
	pair<ll,int>T[q];
	rep(i, q) {
		string x;
		cin >> x;
		ll p=0;
		for(auto j : x) {
			p*=3;
			if(j=='0') ++p;
			if(j=='1') p+=2;
		}
		T[i]={p, i};
	}
	sort(T, T+q);
	vector<ll>V(q);
	vector<int>ans(q);
	rep(i, q) V[i]=T[i].st;
	ll akt=1;
	rep(i, l-1) akt*=3;
	solve(V, ans, 0, n-1, akt);
	rep(i, q) T[i]={T[i].nd, ans[i]};
	sort(T, T+q);
	rep(i, q) cout << T[i].nd << '\n';
}

Compilation message

snake_escaping.cpp: In function 'void solve(std::vector<long long int>&, std::vector<int>&, int, int, ll)':
snake_escaping.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
snake_escaping.cpp:18:2: note: in expansion of macro 'rep'
   18 |  rep(i, V.size()) {
      |  ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 365 ms 42468 KB Output is correct
12 Correct 412 ms 42184 KB Output is correct
13 Correct 388 ms 41468 KB Output is correct
14 Correct 377 ms 41572 KB Output is correct
15 Correct 395 ms 42640 KB Output is correct
16 Correct 382 ms 41800 KB Output is correct
17 Correct 402 ms 41876 KB Output is correct
18 Correct 236 ms 43460 KB Output is correct
19 Correct 385 ms 40512 KB Output is correct
20 Correct 361 ms 42256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 365 ms 42468 KB Output is correct
12 Correct 412 ms 42184 KB Output is correct
13 Correct 388 ms 41468 KB Output is correct
14 Correct 377 ms 41572 KB Output is correct
15 Correct 395 ms 42640 KB Output is correct
16 Correct 382 ms 41800 KB Output is correct
17 Correct 402 ms 41876 KB Output is correct
18 Correct 236 ms 43460 KB Output is correct
19 Correct 385 ms 40512 KB Output is correct
20 Correct 361 ms 42256 KB Output is correct
21 Correct 403 ms 45540 KB Output is correct
22 Correct 418 ms 45800 KB Output is correct
23 Correct 444 ms 47616 KB Output is correct
24 Correct 432 ms 45724 KB Output is correct
25 Correct 421 ms 47004 KB Output is correct
26 Correct 450 ms 48232 KB Output is correct
27 Correct 502 ms 56620 KB Output is correct
28 Correct 237 ms 47592 KB Output is correct
29 Correct 386 ms 43496 KB Output is correct
30 Correct 371 ms 45892 KB Output is correct
31 Correct 458 ms 49304 KB Output is correct
32 Correct 462 ms 46960 KB Output is correct
33 Correct 380 ms 45004 KB Output is correct
34 Correct 470 ms 51100 KB Output is correct
35 Correct 505 ms 56528 KB Output is correct
36 Correct 236 ms 43452 KB Output is correct
37 Correct 414 ms 45532 KB Output is correct
38 Correct 402 ms 43612 KB Output is correct
39 Correct 436 ms 47148 KB Output is correct
40 Correct 449 ms 46112 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 294 ms 9452 KB Output is correct
12 Correct 466 ms 8928 KB Output is correct
13 Correct 395 ms 6816 KB Output is correct
14 Correct 790 ms 7380 KB Output is correct
15 Execution timed out 2017 ms 10152 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 365 ms 42468 KB Output is correct
12 Correct 412 ms 42184 KB Output is correct
13 Correct 388 ms 41468 KB Output is correct
14 Correct 377 ms 41572 KB Output is correct
15 Correct 395 ms 42640 KB Output is correct
16 Correct 382 ms 41800 KB Output is correct
17 Correct 402 ms 41876 KB Output is correct
18 Correct 236 ms 43460 KB Output is correct
19 Correct 385 ms 40512 KB Output is correct
20 Correct 361 ms 42256 KB Output is correct
21 Correct 403 ms 45540 KB Output is correct
22 Correct 418 ms 45800 KB Output is correct
23 Correct 444 ms 47616 KB Output is correct
24 Correct 432 ms 45724 KB Output is correct
25 Correct 421 ms 47004 KB Output is correct
26 Correct 450 ms 48232 KB Output is correct
27 Correct 502 ms 56620 KB Output is correct
28 Correct 237 ms 47592 KB Output is correct
29 Correct 386 ms 43496 KB Output is correct
30 Correct 371 ms 45892 KB Output is correct
31 Correct 458 ms 49304 KB Output is correct
32 Correct 462 ms 46960 KB Output is correct
33 Correct 380 ms 45004 KB Output is correct
34 Correct 470 ms 51100 KB Output is correct
35 Correct 505 ms 56528 KB Output is correct
36 Correct 236 ms 43452 KB Output is correct
37 Correct 414 ms 45532 KB Output is correct
38 Correct 402 ms 43612 KB Output is correct
39 Correct 436 ms 47148 KB Output is correct
40 Correct 449 ms 46112 KB Output is correct
41 Correct 294 ms 9452 KB Output is correct
42 Correct 466 ms 8928 KB Output is correct
43 Correct 395 ms 6816 KB Output is correct
44 Correct 790 ms 7380 KB Output is correct
45 Execution timed out 2017 ms 10152 KB Time limit exceeded
46 Halted 0 ms 0 KB -