oj.uz

답안 #376478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376478 2021-03-11T14:34:39 Z astoria Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 643 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];
	}
	
	if(l>10) return 0;
	
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 748 KB Output is correct
2 Correct 360 ms 748 KB Output is correct
3 Correct 352 ms 876 KB Output is correct
4 Correct 360 ms 852 KB Output is correct
5 Correct 374 ms 876 KB Output is correct
6 Correct 357 ms 876 KB Output is correct
7 Correct 367 ms 876 KB Output is correct
8 Correct 359 ms 876 KB Output is correct
9 Correct 355 ms 748 KB Output is correct
10 Correct 382 ms 908 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 748 KB Output is correct
2 Correct 360 ms 748 KB Output is correct
3 Correct 352 ms 876 KB Output is correct
4 Correct 360 ms 852 KB Output is correct
5 Correct 374 ms 876 KB Output is correct
6 Correct 357 ms 876 KB Output is correct
7 Correct 367 ms 876 KB Output is correct
8 Correct 359 ms 876 KB Output is correct
9 Correct 355 ms 748 KB Output is correct
10 Correct 382 ms 908 KB Output is correct
11 Correct 596 ms 4820 KB Output is correct
12 Correct 643 ms 4564 KB Output is correct
13 Correct 604 ms 3948 KB Output is correct
14 Correct 614 ms 3820 KB Output is correct
15 Correct 588 ms 4844 KB Output is correct
16 Correct 618 ms 4076 KB Output is correct
17 Correct 633 ms 3948 KB Output is correct
18 Correct 548 ms 5868 KB Output is correct
19 Correct 589 ms 2796 KB Output is correct
20 Correct 602 ms 4460 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 748 KB Output is correct
2 Correct 360 ms 748 KB Output is correct
3 Correct 352 ms 876 KB Output is correct
4 Correct 360 ms 852 KB Output is correct
5 Correct 374 ms 876 KB Output is correct
6 Correct 357 ms 876 KB Output is correct
7 Correct 367 ms 876 KB Output is correct
8 Correct 359 ms 876 KB Output is correct
9 Correct 355 ms 748 KB Output is correct
10 Correct 382 ms 908 KB Output is correct
11 Correct 596 ms 4820 KB Output is correct
12 Correct 643 ms 4564 KB Output is correct
13 Correct 604 ms 3948 KB Output is correct
14 Correct 614 ms 3820 KB Output is correct
15 Correct 588 ms 4844 KB Output is correct
16 Correct 618 ms 4076 KB Output is correct
17 Correct 633 ms 3948 KB Output is correct
18 Correct 548 ms 5868 KB Output is correct
19 Correct 589 ms 2796 KB Output is correct
20 Correct 602 ms 4460 KB Output is correct
21 Incorrect 8 ms 12908 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 748 KB Output is correct
2 Correct 360 ms 748 KB Output is correct
3 Correct 352 ms 876 KB Output is correct
4 Correct 360 ms 852 KB Output is correct
5 Correct 374 ms 876 KB Output is correct
6 Correct 357 ms 876 KB Output is correct
7 Correct 367 ms 876 KB Output is correct
8 Correct 359 ms 876 KB Output is correct
9 Correct 355 ms 748 KB Output is correct
10 Correct 382 ms 908 KB Output is correct
11 Runtime error 17 ms 11152 KB Execution killed with signal 7
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 748 KB Output is correct
2 Correct 360 ms 748 KB Output is correct
3 Correct 352 ms 876 KB Output is correct
4 Correct 360 ms 852 KB Output is correct
5 Correct 374 ms 876 KB Output is correct
6 Correct 357 ms 876 KB Output is correct
7 Correct 367 ms 876 KB Output is correct
8 Correct 359 ms 876 KB Output is correct
9 Correct 355 ms 748 KB Output is correct
10 Correct 382 ms 908 KB Output is correct
11 Correct 596 ms 4820 KB Output is correct
12 Correct 643 ms 4564 KB Output is correct
13 Correct 604 ms 3948 KB Output is correct
14 Correct 614 ms 3820 KB Output is correct
15 Correct 588 ms 4844 KB Output is correct
16 Correct 618 ms 4076 KB Output is correct
17 Correct 633 ms 3948 KB Output is correct
18 Correct 548 ms 5868 KB Output is correct
19 Correct 589 ms 2796 KB Output is correct
20 Correct 602 ms 4460 KB Output is correct
21 Incorrect 8 ms 12908 KB Output isn't correct
22 Halted 0 ms 0 KB -