oj.uz

Submission #521630

# Submission time Handle Problem Language Result Execution time Memory
521630 2022-02-02T15:34:26 Z AdamGS Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 38752 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
#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<uint>&V, vector<int>&ans, int l, int r, uint 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;
		V[i]%=akt;
	}
	vector<uint>zero;
	int l1=0, l2=0;
	while(l1<ile1 && l2<ile2) {
		if(V[l1]<=V[ile1+l2]) {
			if(V[l1]==V[ile1+l2]) ++l2;
			zero.pb(V[l1]);
			++l1;
		} else {
			zero.pb(V[ile1+l2]);
			++l2;
		}
	}
	while(l1<ile1) {
		zero.pb(V[l1]); ++l1;
	}
	while(l2<ile2) {
		zero.pb(V[ile1+l2]); ++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]) ++l1;
		ans[i]+=zans[l1];
	}
	l1=0;
	rep(i, ile2) {
		while(zero[l1]<V[ile1+i]) ++l1;
		ans[ile1+i]+=zans[l1];
	}
	zero.resize(0);
	l1=0; l2=0;
	while(l1<ile1 && l2<ile3) {
		if(V[l1]<=V[ile1+ile2+l2]) {
			if(V[l1]==V[ile1+ile2+l2]) ++l2;
			zero.pb(V[l1]);
			++l1;
		} else {
			zero.pb(V[ile1+ile2+l2]);
			++l2;
		}
	}
	while(l1<ile1) {
		zero.pb(V[l1]); ++l1;
	}
	while(l2<ile3) {
		zero.pb(V[ile1+ile2+l2]); ++l2;
	}
	rep(i, zans.size()) zans[i]=0;
	zans.resize(zero.size(), 0);
	solve(zero, zans, (l+r)/2+1, r, akt/3);
	l1=0;
	rep(i, ile1) {
		while(zero[l1]<V[i]) ++l1;
		ans[i]+=zans[l1];
	}
	l1=0;
	rep(i, ile3) {
		while(zero[l1]<V[ile1+ile2+i]) ++l1;
		ans[ile1+ile2+i]+=zans[l1];
	}
	rep(i, ile2) V[ile1+i]+=akt;
	rep(i, ile3) V[ile1+ile2+i]+=2*akt;
}
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<uint,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);
	uint akt=1;
	rep(i, l-1) akt*=3;
	vector<uint>V;
	V.pb(T[0].st);
	for(int i=1; i<q; ++i) if(T[i].st!=T[i-1].st) V.pb(T[i].st);
	vector<int>ans(V.size());
	solve(V, ans, 0, n-1, akt);
	int l1=0;
	rep(i, q) {
		while(V[l1]<T[i].st) ++l1;
		T[i]={T[i].nd, ans[l1]};
	}
	sort(T, T+q);
	rep(i, q) cout << T[i].nd << '\n';
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 309 ms 12080 KB Output is correct
12 Correct 353 ms 11824 KB Output is correct
13 Correct 357 ms 11216 KB Output is correct
14 Correct 341 ms 11280 KB Output is correct
15 Correct 339 ms 12100 KB Output is correct
16 Correct 349 ms 11516 KB Output is correct
17 Correct 372 ms 11896 KB Output is correct
18 Correct 189 ms 13120 KB Output is correct
19 Correct 328 ms 10048 KB Output is correct
20 Correct 311 ms 11716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 309 ms 12080 KB Output is correct
12 Correct 353 ms 11824 KB Output is correct
13 Correct 357 ms 11216 KB Output is correct
14 Correct 341 ms 11280 KB Output is correct
15 Correct 339 ms 12100 KB Output is correct
16 Correct 349 ms 11516 KB Output is correct
17 Correct 372 ms 11896 KB Output is correct
18 Correct 189 ms 13120 KB Output is correct
19 Correct 328 ms 10048 KB Output is correct
20 Correct 311 ms 11716 KB Output is correct
21 Correct 329 ms 12236 KB Output is correct
22 Correct 392 ms 12360 KB Output is correct
23 Correct 407 ms 14332 KB Output is correct
24 Correct 397 ms 12888 KB Output is correct
25 Correct 373 ms 13856 KB Output is correct
26 Correct 406 ms 17696 KB Output is correct
27 Correct 430 ms 23004 KB Output is correct
28 Correct 189 ms 14156 KB Output is correct
29 Correct 362 ms 10308 KB Output is correct
30 Correct 328 ms 12356 KB Output is correct
31 Correct 403 ms 15280 KB Output is correct
32 Correct 398 ms 14152 KB Output is correct
33 Correct 361 ms 11668 KB Output is correct
34 Correct 410 ms 16660 KB Output is correct
35 Correct 450 ms 23020 KB Output is correct
36 Correct 184 ms 10052 KB Output is correct
37 Correct 367 ms 12100 KB Output is correct
38 Correct 380 ms 10308 KB Output is correct
39 Correct 380 ms 14268 KB Output is correct
40 Correct 382 ms 12816 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 198 ms 4388 KB Output is correct
12 Correct 293 ms 4400 KB Output is correct
13 Correct 290 ms 3428 KB Output is correct
14 Correct 570 ms 3464 KB Output is correct
15 Correct 1359 ms 4464 KB Output is correct
16 Correct 711 ms 3556 KB Output is correct
17 Correct 733 ms 3572 KB Output is correct
18 Correct 90 ms 2376 KB Output is correct
19 Correct 54 ms 2608 KB Output is correct
20 Correct 292 ms 4748 KB Output is correct
21 Correct 1109 ms 3744 KB Output is correct
22 Correct 588 ms 3684 KB Output is correct
23 Correct 106 ms 4196 KB Output is correct
24 Correct 477 ms 3308 KB Output is correct
25 Correct 721 ms 3416 KB Output is correct
26 Correct 14 ms 2408 KB Output is correct
27 Correct 197 ms 4112 KB Output is correct
28 Correct 56 ms 2660 KB Output is correct
29 Correct 312 ms 3916 KB Output is correct
30 Correct 443 ms 3284 KB Output is correct
31 Correct 102 ms 3992 KB Output is correct
32 Correct 714 ms 3428 KB Output is correct
33 Correct 728 ms 3492 KB Output is correct
34 Correct 13 ms 2408 KB Output is correct
35 Correct 735 ms 3444 KB Output is correct
36 Correct 731 ms 3584 KB Output is correct
37 Correct 730 ms 3588 KB Output is correct
38 Correct 725 ms 3428 KB Output is correct
39 Correct 721 ms 3324 KB Output is correct
40 Correct 724 ms 3432 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 309 ms 12080 KB Output is correct
12 Correct 353 ms 11824 KB Output is correct
13 Correct 357 ms 11216 KB Output is correct
14 Correct 341 ms 11280 KB Output is correct
15 Correct 339 ms 12100 KB Output is correct
16 Correct 349 ms 11516 KB Output is correct
17 Correct 372 ms 11896 KB Output is correct
18 Correct 189 ms 13120 KB Output is correct
19 Correct 328 ms 10048 KB Output is correct
20 Correct 311 ms 11716 KB Output is correct
21 Correct 329 ms 12236 KB Output is correct
22 Correct 392 ms 12360 KB Output is correct
23 Correct 407 ms 14332 KB Output is correct
24 Correct 397 ms 12888 KB Output is correct
25 Correct 373 ms 13856 KB Output is correct
26 Correct 406 ms 17696 KB Output is correct
27 Correct 430 ms 23004 KB Output is correct
28 Correct 189 ms 14156 KB Output is correct
29 Correct 362 ms 10308 KB Output is correct
30 Correct 328 ms 12356 KB Output is correct
31 Correct 403 ms 15280 KB Output is correct
32 Correct 398 ms 14152 KB Output is correct
33 Correct 361 ms 11668 KB Output is correct
34 Correct 410 ms 16660 KB Output is correct
35 Correct 450 ms 23020 KB Output is correct
36 Correct 184 ms 10052 KB Output is correct
37 Correct 367 ms 12100 KB Output is correct
38 Correct 380 ms 10308 KB Output is correct
39 Correct 380 ms 14268 KB Output is correct
40 Correct 382 ms 12816 KB Output is correct
41 Correct 198 ms 4388 KB Output is correct
42 Correct 293 ms 4400 KB Output is correct
43 Correct 290 ms 3428 KB Output is correct
44 Correct 570 ms 3464 KB Output is correct
45 Correct 1359 ms 4464 KB Output is correct
46 Correct 711 ms 3556 KB Output is correct
47 Correct 733 ms 3572 KB Output is correct
48 Correct 90 ms 2376 KB Output is correct
49 Correct 54 ms 2608 KB Output is correct
50 Correct 292 ms 4748 KB Output is correct
51 Correct 1109 ms 3744 KB Output is correct
52 Correct 588 ms 3684 KB Output is correct
53 Correct 106 ms 4196 KB Output is correct
54 Correct 477 ms 3308 KB Output is correct
55 Correct 721 ms 3416 KB Output is correct
56 Correct 14 ms 2408 KB Output is correct
57 Correct 197 ms 4112 KB Output is correct
58 Correct 56 ms 2660 KB Output is correct
59 Correct 312 ms 3916 KB Output is correct
60 Correct 443 ms 3284 KB Output is correct
61 Correct 102 ms 3992 KB Output is correct
62 Correct 714 ms 3428 KB Output is correct
63 Correct 728 ms 3492 KB Output is correct
64 Correct 13 ms 2408 KB Output is correct
65 Correct 735 ms 3444 KB Output is correct
66 Correct 731 ms 3584 KB Output is correct
67 Correct 730 ms 3588 KB Output is correct
68 Correct 725 ms 3428 KB Output is correct
69 Correct 721 ms 3324 KB Output is correct
70 Correct 724 ms 3432 KB Output is correct
71 Correct 605 ms 18108 KB Output is correct
72 Correct 784 ms 26976 KB Output is correct
73 Correct 1892 ms 38752 KB Output is correct
74 Execution timed out 2085 ms 37204 KB Time limit exceeded
75 Halted 0 ms 0 KB -