oj.uz

Submission #376475

# Submission time Handle Problem Language Result Execution time Memory
376475 2021-03-11T14:33:28 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];
		}
	}
	
	if(l>10) return 0;
	
	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 367 ms 852 KB Output is correct
2 Correct 383 ms 768 KB Output is correct
3 Correct 372 ms 876 KB Output is correct
4 Correct 372 ms 748 KB Output is correct
5 Correct 370 ms 852 KB Output is correct
6 Correct 363 ms 852 KB Output is correct
7 Correct 373 ms 852 KB Output is correct
8 Correct 372 ms 748 KB Output is correct
9 Correct 376 ms 852 KB Output is correct
10 Correct 362 ms 748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 852 KB Output is correct
2 Correct 383 ms 768 KB Output is correct
3 Correct 372 ms 876 KB Output is correct
4 Correct 372 ms 748 KB Output is correct
5 Correct 370 ms 852 KB Output is correct
6 Correct 363 ms 852 KB Output is correct
7 Correct 373 ms 852 KB Output is correct
8 Correct 372 ms 748 KB Output is correct
9 Correct 376 ms 852 KB Output is correct
10 Correct 362 ms 748 KB Output is correct
11 Correct 625 ms 4844 KB Output is correct
12 Correct 631 ms 4436 KB Output is correct
13 Correct 619 ms 3716 KB Output is correct
14 Correct 613 ms 3924 KB Output is correct
15 Correct 604 ms 5100 KB Output is correct
16 Correct 644 ms 4076 KB Output is correct
17 Correct 628 ms 4180 KB Output is correct
18 Correct 553 ms 5868 KB Output is correct
19 Correct 607 ms 3052 KB Output is correct
20 Correct 604 ms 4532 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 852 KB Output is correct
2 Correct 383 ms 768 KB Output is correct
3 Correct 372 ms 876 KB Output is correct
4 Correct 372 ms 748 KB Output is correct
5 Correct 370 ms 852 KB Output is correct
6 Correct 363 ms 852 KB Output is correct
7 Correct 373 ms 852 KB Output is correct
8 Correct 372 ms 748 KB Output is correct
9 Correct 376 ms 852 KB Output is correct
10 Correct 362 ms 748 KB Output is correct
11 Correct 625 ms 4844 KB Output is correct
12 Correct 631 ms 4436 KB Output is correct
13 Correct 619 ms 3716 KB Output is correct
14 Correct 613 ms 3924 KB Output is correct
15 Correct 604 ms 5100 KB Output is correct
16 Correct 644 ms 4076 KB Output is correct
17 Correct 628 ms 4180 KB Output is correct
18 Correct 553 ms 5868 KB Output is correct
19 Correct 607 ms 3052 KB Output is correct
20 Correct 604 ms 4532 KB Output is correct
21 Execution timed out 2091 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 367 ms 852 KB Output is correct
2 Correct 383 ms 768 KB Output is correct
3 Correct 372 ms 876 KB Output is correct
4 Correct 372 ms 748 KB Output is correct
5 Correct 370 ms 852 KB Output is correct
6 Correct 363 ms 852 KB Output is correct
7 Correct 373 ms 852 KB Output is correct
8 Correct 372 ms 748 KB Output is correct
9 Correct 376 ms 852 KB Output is correct
10 Correct 362 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 367 ms 852 KB Output is correct
2 Correct 383 ms 768 KB Output is correct
3 Correct 372 ms 876 KB Output is correct
4 Correct 372 ms 748 KB Output is correct
5 Correct 370 ms 852 KB Output is correct
6 Correct 363 ms 852 KB Output is correct
7 Correct 373 ms 852 KB Output is correct
8 Correct 372 ms 748 KB Output is correct
9 Correct 376 ms 852 KB Output is correct
10 Correct 362 ms 748 KB Output is correct
11 Correct 625 ms 4844 KB Output is correct
12 Correct 631 ms 4436 KB Output is correct
13 Correct 619 ms 3716 KB Output is correct
14 Correct 613 ms 3924 KB Output is correct
15 Correct 604 ms 5100 KB Output is correct
16 Correct 644 ms 4076 KB Output is correct
17 Correct 628 ms 4180 KB Output is correct
18 Correct 553 ms 5868 KB Output is correct
19 Correct 607 ms 3052 KB Output is correct
20 Correct 604 ms 4532 KB Output is correct
21 Execution timed out 2091 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -