oj.uz

답안 #376487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376487 2021-03-11T14:46:18 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;
	
	if(l<=10) goto acn;
	
	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];
	}*/
	
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 748 KB Output is correct
2 Correct 451 ms 748 KB Output is correct
3 Correct 451 ms 768 KB Output is correct
4 Correct 449 ms 748 KB Output is correct
5 Correct 470 ms 876 KB Output is correct
6 Correct 456 ms 748 KB Output is correct
7 Correct 455 ms 876 KB Output is correct
8 Correct 445 ms 876 KB Output is correct
9 Correct 445 ms 852 KB Output is correct
10 Correct 447 ms 748 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 748 KB Output is correct
2 Correct 451 ms 748 KB Output is correct
3 Correct 451 ms 768 KB Output is correct
4 Correct 449 ms 748 KB Output is correct
5 Correct 470 ms 876 KB Output is correct
6 Correct 456 ms 748 KB Output is correct
7 Correct 455 ms 876 KB Output is correct
8 Correct 445 ms 876 KB Output is correct
9 Correct 445 ms 852 KB Output is correct
10 Correct 447 ms 748 KB Output is correct
11 Correct 682 ms 4948 KB Output is correct
12 Correct 741 ms 4460 KB Output is correct
13 Correct 717 ms 3692 KB Output is correct
14 Correct 702 ms 3820 KB Output is correct
15 Correct 682 ms 4844 KB Output is correct
16 Correct 706 ms 4076 KB Output is correct
17 Correct 752 ms 3948 KB Output is correct
18 Correct 642 ms 5868 KB Output is correct
19 Correct 668 ms 2796 KB Output is correct
20 Correct 678 ms 4460 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 748 KB Output is correct
2 Correct 451 ms 748 KB Output is correct
3 Correct 451 ms 768 KB Output is correct
4 Correct 449 ms 748 KB Output is correct
5 Correct 470 ms 876 KB Output is correct
6 Correct 456 ms 748 KB Output is correct
7 Correct 455 ms 876 KB Output is correct
8 Correct 445 ms 876 KB Output is correct
9 Correct 445 ms 852 KB Output is correct
10 Correct 447 ms 748 KB Output is correct
11 Correct 682 ms 4948 KB Output is correct
12 Correct 741 ms 4460 KB Output is correct
13 Correct 717 ms 3692 KB Output is correct
14 Correct 702 ms 3820 KB Output is correct
15 Correct 682 ms 4844 KB Output is correct
16 Correct 706 ms 4076 KB Output is correct
17 Correct 752 ms 3948 KB Output is correct
18 Correct 642 ms 5868 KB Output is correct
19 Correct 668 ms 2796 KB Output is correct
20 Correct 678 ms 4460 KB Output is correct
21 Execution timed out 2078 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 748 KB Output is correct
2 Correct 451 ms 748 KB Output is correct
3 Correct 451 ms 768 KB Output is correct
4 Correct 449 ms 748 KB Output is correct
5 Correct 470 ms 876 KB Output is correct
6 Correct 456 ms 748 KB Output is correct
7 Correct 455 ms 876 KB Output is correct
8 Correct 445 ms 876 KB Output is correct
9 Correct 445 ms 852 KB Output is correct
10 Correct 447 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

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 748 KB Output is correct
2 Correct 451 ms 748 KB Output is correct
3 Correct 451 ms 768 KB Output is correct
4 Correct 449 ms 748 KB Output is correct
5 Correct 470 ms 876 KB Output is correct
6 Correct 456 ms 748 KB Output is correct
7 Correct 455 ms 876 KB Output is correct
8 Correct 445 ms 876 KB Output is correct
9 Correct 445 ms 852 KB Output is correct
10 Correct 447 ms 748 KB Output is correct
11 Correct 682 ms 4948 KB Output is correct
12 Correct 741 ms 4460 KB Output is correct
13 Correct 717 ms 3692 KB Output is correct
14 Correct 702 ms 3820 KB Output is correct
15 Correct 682 ms 4844 KB Output is correct
16 Correct 706 ms 4076 KB Output is correct
17 Correct 752 ms 3948 KB Output is correct
18 Correct 642 ms 5868 KB Output is correct
19 Correct 668 ms 2796 KB Output is correct
20 Correct 678 ms 4460 KB Output is correct
21 Execution timed out 2078 ms 12908 KB Time limit exceeded
22 Halted 0 ms 0 KB -