oj.uz

Submission #376484

# Submission time Handle Problem Language Result Execution time Memory
376484 2021-03-11T14:39:19 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);
	
	if(l<=10) goto acn;
	
	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];
	}
	
	acn :
	
	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 357 ms 748 KB Output is correct
2 Correct 351 ms 876 KB Output is correct
3 Correct 361 ms 748 KB Output is correct
4 Correct 358 ms 876 KB Output is correct
5 Correct 356 ms 876 KB Output is correct
6 Correct 346 ms 876 KB Output is correct
7 Correct 356 ms 876 KB Output is correct
8 Correct 361 ms 876 KB Output is correct
9 Correct 358 ms 876 KB Output is correct
10 Correct 351 ms 748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 748 KB Output is correct
2 Correct 351 ms 876 KB Output is correct
3 Correct 361 ms 748 KB Output is correct
4 Correct 358 ms 876 KB Output is correct
5 Correct 356 ms 876 KB Output is correct
6 Correct 346 ms 876 KB Output is correct
7 Correct 356 ms 876 KB Output is correct
8 Correct 361 ms 876 KB Output is correct
9 Correct 358 ms 876 KB Output is correct
10 Correct 351 ms 748 KB Output is correct
11 Correct 591 ms 4876 KB Output is correct
12 Correct 594 ms 4588 KB Output is correct
13 Correct 588 ms 3804 KB Output is correct
14 Correct 610 ms 3820 KB Output is correct
15 Correct 600 ms 4828 KB Output is correct
16 Correct 650 ms 4052 KB Output is correct
17 Correct 631 ms 3948 KB Output is correct
18 Correct 551 ms 5996 KB Output is correct
19 Correct 577 ms 2796 KB Output is correct
20 Correct 586 ms 4460 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 748 KB Output is correct
2 Correct 351 ms 876 KB Output is correct
3 Correct 361 ms 748 KB Output is correct
4 Correct 358 ms 876 KB Output is correct
5 Correct 356 ms 876 KB Output is correct
6 Correct 346 ms 876 KB Output is correct
7 Correct 356 ms 876 KB Output is correct
8 Correct 361 ms 876 KB Output is correct
9 Correct 358 ms 876 KB Output is correct
10 Correct 351 ms 748 KB Output is correct
11 Correct 591 ms 4876 KB Output is correct
12 Correct 594 ms 4588 KB Output is correct
13 Correct 588 ms 3804 KB Output is correct
14 Correct 610 ms 3820 KB Output is correct
15 Correct 600 ms 4828 KB Output is correct
16 Correct 650 ms 4052 KB Output is correct
17 Correct 631 ms 3948 KB Output is correct
18 Correct 551 ms 5996 KB Output is correct
19 Correct 577 ms 2796 KB Output is correct
20 Correct 586 ms 4460 KB Output is correct
21 Execution timed out 2084 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 357 ms 748 KB Output is correct
2 Correct 351 ms 876 KB Output is correct
3 Correct 361 ms 748 KB Output is correct
4 Correct 358 ms 876 KB Output is correct
5 Correct 356 ms 876 KB Output is correct
6 Correct 346 ms 876 KB Output is correct
7 Correct 356 ms 876 KB Output is correct
8 Correct 361 ms 876 KB Output is correct
9 Correct 358 ms 876 KB Output is correct
10 Correct 351 ms 748 KB Output is correct
11 Runtime error 13 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 357 ms 748 KB Output is correct
2 Correct 351 ms 876 KB Output is correct
3 Correct 361 ms 748 KB Output is correct
4 Correct 358 ms 876 KB Output is correct
5 Correct 356 ms 876 KB Output is correct
6 Correct 346 ms 876 KB Output is correct
7 Correct 356 ms 876 KB Output is correct
8 Correct 361 ms 876 KB Output is correct
9 Correct 358 ms 876 KB Output is correct
10 Correct 351 ms 748 KB Output is correct
11 Correct 591 ms 4876 KB Output is correct
12 Correct 594 ms 4588 KB Output is correct
13 Correct 588 ms 3804 KB Output is correct
14 Correct 610 ms 3820 KB Output is correct
15 Correct 600 ms 4828 KB Output is correct
16 Correct 650 ms 4052 KB Output is correct
17 Correct 631 ms 3948 KB Output is correct
18 Correct 551 ms 5996 KB Output is correct
19 Correct 577 ms 2796 KB Output is correct
20 Correct 586 ms 4460 KB Output is correct
21 Execution timed out 2084 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -