oj.uz

Submission #376483

# Submission time Handle Problem Language Result Execution time Memory
376483 2021-03-11T14:38:11 Z astoria Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 12908 KB 
#include "bits/stdc++.h"
using namespace std;

int l,q,n;
int pw[25]; 

int fast_mod(const int input, const int ceil) {
    // apply the modulo operator only when needed
    // (i.e. when the input is greater than the ceiling)
    return input >= ceil ? input % ceil : input;
    // NB: the assumption here is that the numbers are positive
}

bool comp(int a, int b){
	vector<int> x,y;
	int cntx=0,cnty=0;
	for(int j=0; j<l; j++){
		int cr = fast_mod(a,3); a/=3;
		if(cr==2) cntx++;
	}
	for(int j=0; j<l; j++){
		int cr = fast_mod(b,3); b/=3;
		if(cr==2) cnty++;
	}
	return cntx<cnty;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>l>>q; n=1<<l;
	string s; cin>>s;
	int tox[n];
	for(int i=0; i<n; i++) tox[i] = s[i]-'0';
	
	pw[0]=1;
	int k=1; for(int i=1; i<=l; i++){ k*=3; pw[i]=k;}
	int ans[k]; memset(ans,0,sizeof(ans));
	
	int ord[k];
	for(int i=0; i<k; i++) ord[i]=i;
		
	sort(ord,ord+k,comp);
	
	for(int i=0; i<n; i++){
		int v = ord[i], vk=v;
		int tot = 0;
		for(int j=0; j<l; j++){
			int cr = fast_mod(v,3); v/=3;
			tot += ((1<<j)*cr);
		}
		ans[vk] = tox[tot];
	}
		
	for(int ahc=n; ahc<k; ahc++){
		int v = ord[ahc], tk = ord[ahc], tt = ord[ahc], vk = ord[ahc];
		for(int i=0; i<l; i++){
			int cr = fast_mod(v,3); v/=3;
			if(cr==2){
				tk-=(2*pw[i]);
				tt-=(1*pw[i]);
				break;
			}
		}
		ans[vk] = ans[tk]+ans[tt];
	}
	
	/*	
	for(int ahc=0; ahc<k; ahc++){
		vector<int> v; int cr=ahc;
		for(int j=0; j<l; j++){
			v.push_back(cr%3); cr/=3;
		}
		for(int i=0; i<n; i++){
			bitset<13> b(i); bool f=1;
			for(int j=0; j<l; j++){
				if(v[j]!=2 && (b[j]!=v[j])){ f=0; break;}
			}
			if(f) ans[ahc] += tox[i];
		}
	}*/
		
	for(int ahc=0; ahc<q; ahc++){
		string s; cin>>s;
		int qr=0;
		for(int i=0; i<l; i++){
			int pwer = l-i-1;
			if(s[i]=='1') qr += (pw[pwer]);
			if(s[i]=='?') qr += (2*pw[pwer]);
		}
		cout<<ans[qr]<<"\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 748 KB Output is correct
2 Correct 56 ms 748 KB Output is correct
3 Correct 132 ms 876 KB Output is correct
4 Correct 61 ms 748 KB Output is correct
5 Correct 66 ms 876 KB Output is correct
6 Correct 51 ms 748 KB Output is correct
7 Correct 61 ms 748 KB Output is correct
8 Correct 72 ms 876 KB Output is correct
9 Correct 56 ms 748 KB Output is correct
10 Correct 55 ms 852 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 748 KB Output is correct
2 Correct 56 ms 748 KB Output is correct
3 Correct 132 ms 876 KB Output is correct
4 Correct 61 ms 748 KB Output is correct
5 Correct 66 ms 876 KB Output is correct
6 Correct 51 ms 748 KB Output is correct
7 Correct 61 ms 748 KB Output is correct
8 Correct 72 ms 876 KB Output is correct
9 Correct 56 ms 748 KB Output is correct
10 Correct 55 ms 852 KB Output is correct
11 Correct 293 ms 4844 KB Output is correct
12 Correct 425 ms 4460 KB Output is correct
13 Correct 298 ms 3692 KB Output is correct
14 Correct 340 ms 3888 KB Output is correct
15 Correct 294 ms 4836 KB Output is correct
16 Correct 320 ms 4024 KB Output is correct
17 Correct 350 ms 3948 KB Output is correct
18 Correct 276 ms 6000 KB Output is correct
19 Correct 280 ms 2796 KB Output is correct
20 Correct 309 ms 4436 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 748 KB Output is correct
2 Correct 56 ms 748 KB Output is correct
3 Correct 132 ms 876 KB Output is correct
4 Correct 61 ms 748 KB Output is correct
5 Correct 66 ms 876 KB Output is correct
6 Correct 51 ms 748 KB Output is correct
7 Correct 61 ms 748 KB Output is correct
8 Correct 72 ms 876 KB Output is correct
9 Correct 56 ms 748 KB Output is correct
10 Correct 55 ms 852 KB Output is correct
11 Correct 293 ms 4844 KB Output is correct
12 Correct 425 ms 4460 KB Output is correct
13 Correct 298 ms 3692 KB Output is correct
14 Correct 340 ms 3888 KB Output is correct
15 Correct 294 ms 4836 KB Output is correct
16 Correct 320 ms 4024 KB Output is correct
17 Correct 350 ms 3948 KB Output is correct
18 Correct 276 ms 6000 KB Output is correct
19 Correct 280 ms 2796 KB Output is correct
20 Correct 309 ms 4436 KB Output is correct
21 Execution timed out 2090 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 748 KB Output is correct
2 Correct 56 ms 748 KB Output is correct
3 Correct 132 ms 876 KB Output is correct
4 Correct 61 ms 748 KB Output is correct
5 Correct 66 ms 876 KB Output is correct
6 Correct 51 ms 748 KB Output is correct
7 Correct 61 ms 748 KB Output is correct
8 Correct 72 ms 876 KB Output is correct
9 Correct 56 ms 748 KB Output is correct
10 Correct 55 ms 852 KB Output is correct
11 Runtime error 14 ms 11152 KB Execution killed with signal 7
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 748 KB Output is correct
2 Correct 56 ms 748 KB Output is correct
3 Correct 132 ms 876 KB Output is correct
4 Correct 61 ms 748 KB Output is correct
5 Correct 66 ms 876 KB Output is correct
6 Correct 51 ms 748 KB Output is correct
7 Correct 61 ms 748 KB Output is correct
8 Correct 72 ms 876 KB Output is correct
9 Correct 56 ms 748 KB Output is correct
10 Correct 55 ms 852 KB Output is correct
11 Correct 293 ms 4844 KB Output is correct
12 Correct 425 ms 4460 KB Output is correct
13 Correct 298 ms 3692 KB Output is correct
14 Correct 340 ms 3888 KB Output is correct
15 Correct 294 ms 4836 KB Output is correct
16 Correct 320 ms 4024 KB Output is correct
17 Correct 350 ms 3948 KB Output is correct
18 Correct 276 ms 6000 KB Output is correct
19 Correct 280 ms 2796 KB Output is correct
20 Correct 309 ms 4436 KB Output is correct
21 Execution timed out 2090 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -