oj.uz

Submission #376471

# Submission time Handle Problem Language Result Execution time Memory
376471 2021-03-11T14:29:07 Z astoria Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 14572 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;
	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];
	}
	
	/*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 47 ms 748 KB Output is correct
2 Correct 44 ms 748 KB Output is correct
3 Correct 47 ms 748 KB Output is correct
4 Correct 46 ms 748 KB Output is correct
5 Correct 43 ms 748 KB Output is correct
6 Correct 43 ms 748 KB Output is correct
7 Correct 45 ms 852 KB Output is correct
8 Correct 50 ms 748 KB Output is correct
9 Correct 43 ms 768 KB Output is correct
10 Correct 43 ms 748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 748 KB Output is correct
2 Correct 44 ms 748 KB Output is correct
3 Correct 47 ms 748 KB Output is correct
4 Correct 46 ms 748 KB Output is correct
5 Correct 43 ms 748 KB Output is correct
6 Correct 43 ms 748 KB Output is correct
7 Correct 45 ms 852 KB Output is correct
8 Correct 50 ms 748 KB Output is correct
9 Correct 43 ms 768 KB Output is correct
10 Correct 43 ms 748 KB Output is correct
11 Correct 283 ms 4844 KB Output is correct
12 Correct 302 ms 4460 KB Output is correct
13 Correct 300 ms 3820 KB Output is correct
14 Correct 305 ms 3820 KB Output is correct
15 Correct 319 ms 4996 KB Output is correct
16 Correct 311 ms 3948 KB Output is correct
17 Correct 323 ms 3948 KB Output is correct
18 Correct 249 ms 5996 KB Output is correct
19 Correct 282 ms 2796 KB Output is correct
20 Correct 293 ms 4460 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 748 KB Output is correct
2 Correct 44 ms 748 KB Output is correct
3 Correct 47 ms 748 KB Output is correct
4 Correct 46 ms 748 KB Output is correct
5 Correct 43 ms 748 KB Output is correct
6 Correct 43 ms 748 KB Output is correct
7 Correct 45 ms 852 KB Output is correct
8 Correct 50 ms 748 KB Output is correct
9 Correct 43 ms 768 KB Output is correct
10 Correct 43 ms 748 KB Output is correct
11 Correct 283 ms 4844 KB Output is correct
12 Correct 302 ms 4460 KB Output is correct
13 Correct 300 ms 3820 KB Output is correct
14 Correct 305 ms 3820 KB Output is correct
15 Correct 319 ms 4996 KB Output is correct
16 Correct 311 ms 3948 KB Output is correct
17 Correct 323 ms 3948 KB Output is correct
18 Correct 249 ms 5996 KB Output is correct
19 Correct 282 ms 2796 KB Output is correct
20 Correct 293 ms 4460 KB Output is correct
21 Execution timed out 2082 ms 14572 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 748 KB Output is correct
2 Correct 44 ms 748 KB Output is correct
3 Correct 47 ms 748 KB Output is correct
4 Correct 46 ms 748 KB Output is correct
5 Correct 43 ms 748 KB Output is correct
6 Correct 43 ms 748 KB Output is correct
7 Correct 45 ms 852 KB Output is correct
8 Correct 50 ms 748 KB Output is correct
9 Correct 43 ms 768 KB Output is correct
10 Correct 43 ms 748 KB Output is correct
11 Runtime error 15 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 47 ms 748 KB Output is correct
2 Correct 44 ms 748 KB Output is correct
3 Correct 47 ms 748 KB Output is correct
4 Correct 46 ms 748 KB Output is correct
5 Correct 43 ms 748 KB Output is correct
6 Correct 43 ms 748 KB Output is correct
7 Correct 45 ms 852 KB Output is correct
8 Correct 50 ms 748 KB Output is correct
9 Correct 43 ms 768 KB Output is correct
10 Correct 43 ms 748 KB Output is correct
11 Correct 283 ms 4844 KB Output is correct
12 Correct 302 ms 4460 KB Output is correct
13 Correct 300 ms 3820 KB Output is correct
14 Correct 305 ms 3820 KB Output is correct
15 Correct 319 ms 4996 KB Output is correct
16 Correct 311 ms 3948 KB Output is correct
17 Correct 323 ms 3948 KB Output is correct
18 Correct 249 ms 5996 KB Output is correct
19 Correct 282 ms 2796 KB Output is correct
20 Correct 293 ms 4460 KB Output is correct
21 Execution timed out 2082 ms 14572 KB Time limit exceeded
22 Halted 0 ms 0 KB -