oj.uz

Submission #376474

# Submission time Handle Problem Language Result Execution time Memory
376474 2021-03-11T14:32:21 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]; 

bool comp(int a, int b){
	vector<int> x,y;
	int cntx=0,cnty=0;
	for(int j=0; j<l; j++){
		int cr = a%3; a/=3;
		if(cr==2) cntx++;
	}
	for(int j=0; j<l; j++){
		int cr = 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;
	
	if(l<=10) goto ahc;
	
	//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 = 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 = v%3; v/=3;
			if(cr==2){
				tk-=(2*pw[i]);
				tt-=(1*pw[i]);
				break;
			}
		}
		ans[vk] = ans[tk]+ans[tt];
	}
	
	ahc :
	
	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 397 ms 852 KB Output is correct
2 Correct 400 ms 876 KB Output is correct
3 Correct 405 ms 748 KB Output is correct
4 Correct 395 ms 876 KB Output is correct
5 Correct 401 ms 876 KB Output is correct
6 Correct 396 ms 876 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 395 ms 876 KB Output is correct
9 Correct 399 ms 852 KB Output is correct
10 Correct 397 ms 876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 852 KB Output is correct
2 Correct 400 ms 876 KB Output is correct
3 Correct 405 ms 748 KB Output is correct
4 Correct 395 ms 876 KB Output is correct
5 Correct 401 ms 876 KB Output is correct
6 Correct 396 ms 876 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 395 ms 876 KB Output is correct
9 Correct 399 ms 852 KB Output is correct
10 Correct 397 ms 876 KB Output is correct
11 Correct 630 ms 4972 KB Output is correct
12 Correct 640 ms 4716 KB Output is correct
13 Correct 646 ms 3820 KB Output is correct
14 Correct 644 ms 3948 KB Output is correct
15 Correct 634 ms 4844 KB Output is correct
16 Correct 665 ms 4076 KB Output is correct
17 Correct 674 ms 3948 KB Output is correct
18 Correct 589 ms 5868 KB Output is correct
19 Correct 613 ms 2924 KB Output is correct
20 Correct 630 ms 4460 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 852 KB Output is correct
2 Correct 400 ms 876 KB Output is correct
3 Correct 405 ms 748 KB Output is correct
4 Correct 395 ms 876 KB Output is correct
5 Correct 401 ms 876 KB Output is correct
6 Correct 396 ms 876 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 395 ms 876 KB Output is correct
9 Correct 399 ms 852 KB Output is correct
10 Correct 397 ms 876 KB Output is correct
11 Correct 630 ms 4972 KB Output is correct
12 Correct 640 ms 4716 KB Output is correct
13 Correct 646 ms 3820 KB Output is correct
14 Correct 644 ms 3948 KB Output is correct
15 Correct 634 ms 4844 KB Output is correct
16 Correct 665 ms 4076 KB Output is correct
17 Correct 674 ms 3948 KB Output is correct
18 Correct 589 ms 5868 KB Output is correct
19 Correct 613 ms 2924 KB Output is correct
20 Correct 630 ms 4460 KB Output is correct
21 Execution timed out 2098 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 397 ms 852 KB Output is correct
2 Correct 400 ms 876 KB Output is correct
3 Correct 405 ms 748 KB Output is correct
4 Correct 395 ms 876 KB Output is correct
5 Correct 401 ms 876 KB Output is correct
6 Correct 396 ms 876 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 395 ms 876 KB Output is correct
9 Correct 399 ms 852 KB Output is correct
10 Correct 397 ms 876 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 397 ms 852 KB Output is correct
2 Correct 400 ms 876 KB Output is correct
3 Correct 405 ms 748 KB Output is correct
4 Correct 395 ms 876 KB Output is correct
5 Correct 401 ms 876 KB Output is correct
6 Correct 396 ms 876 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 395 ms 876 KB Output is correct
9 Correct 399 ms 852 KB Output is correct
10 Correct 397 ms 876 KB Output is correct
11 Correct 630 ms 4972 KB Output is correct
12 Correct 640 ms 4716 KB Output is correct
13 Correct 646 ms 3820 KB Output is correct
14 Correct 644 ms 3948 KB Output is correct
15 Correct 634 ms 4844 KB Output is correct
16 Correct 665 ms 4076 KB Output is correct
17 Correct 674 ms 3948 KB Output is correct
18 Correct 589 ms 5868 KB Output is correct
19 Correct 613 ms 2924 KB Output is correct
20 Correct 630 ms 4460 KB Output is correct
21 Execution timed out 2098 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -