답안 #66808 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66808	2018-08-12T10:33:26 Z	hamzqq9	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	1937 ms	66560 KB

snake_escaping

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000000000
#define MOD 1000000007
#define N 100005
#define MAX 10000006
#define L 12
#define R 8
#define LOG 22
using namespace std;

unsigned short int ans[pw(L)][6566];
char val[pw(20)+3];
int po3[12];
int l,q,n;
int res,value;
char s[pw(20)+3];
int sz;
pair<char,short int> stck[pw(L)+5];

int get_pos_of_2(int value) {

	int cur=0;

	while(value) {

		if(value%3==2) return cur;

		value/=3;

		cur++;

	}

	return -1;

}

int get_val(int bas,int son) {

	int cur=0;

	for(int i=bas;i<=son;i++) {

		cur+=po3[son-i]*(s[i]=='?'?2:(s[i]-'0'));

	}

	return cur;

}

int get_2_rep(int val) {

	int res=0;

	int curpw=1;

	while(val) {

		res+=curpw*(val%3);

		curpw*=2;

		val/=3;

	}

	return res;

}

void back_track(char bit,short int val) {

	stck[sz++]={bit,val};

	while(sz) {

		sz--;

		char bit=stck[sz].st;
		short int val=stck[sz].nd;

		if(bit==-1) {

			res+=ans[val][value];

			continue ;

		}

		if(s[bit]!='?') {
		
			stck[sz++]={bit-1,val+pw(L-1-bit)*(s[bit]=='1')};
		}
		else {

			stck[sz++]={bit-1,val+pw(L-1-bit)};
			stck[sz++]={bit-1,val};

		}

	}

} 

void pre_calc() {

	for(int i=0;i<po3[R];i++) {

		char pos=get_pos_of_2(i);

		short int temp=-1;

		if(pos==-1) temp=get_2_rep(i);

		for(int j=0;j<pw(L);j++) {

			if(pos==-1) {

				ans[j][i]=val[temp+pw(R)*j];

			}
			else {

				ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];

			}

		}

	}

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d %d",&l,&q);

	po3[0]=1;

	for(int i=1;i<=10;i++) po3[i]=po3[i-1]*3;

	n=pw(l);

	scanf("%s",s);

	for(int i=0;i<n;i++) {

		val[i]=s[i]-'0';

	}

	pre_calc();

	while(q--) {

		scanf("%s",s+20-l);

		for(int i=0;i<20-l;i++) s[i]='0';

		res=0;

		value=get_val(L,19);

		back_track(L-1,0);

		printf("%d\n",res);

	}

}

Compilation message

snake_escaping.cpp: In function 'void back_track(char, short int)':
snake_escaping.cpp:106:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(s[bit]!='?') {
           ^
snake_escaping.cpp:108:44: warning: array subscript has type 'char' [-Wchar-subscripts]
    stck[sz++]={bit-1,val+pw(L-1-bit)*(s[bit]=='1')};
                                            ^
snake_escaping.cpp: In function 'void pre_calc()':
snake_escaping.cpp:140:31: warning: array subscript has type 'char' [-Wchar-subscripts]
     ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];
                               ^
snake_escaping.cpp:140:50: warning: array subscript has type 'char' [-Wchar-subscripts]
     ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];
                                                  ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&l,&q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s+20-l);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	52996 KB	Output is correct
2	Correct	544 ms	52996 KB	Output is correct
3	Correct	513 ms	53292 KB	Output is correct
4	Correct	482 ms	53292 KB	Output is correct
5	Correct	478 ms	53292 KB	Output is correct
6	Correct	500 ms	53292 KB	Output is correct
7	Correct	485 ms	53344 KB	Output is correct
8	Correct	484 ms	53344 KB	Output is correct
9	Correct	482 ms	53344 KB	Output is correct
10	Correct	497 ms	53344 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	52996 KB	Output is correct
2	Correct	544 ms	52996 KB	Output is correct
3	Correct	513 ms	53292 KB	Output is correct
4	Correct	482 ms	53292 KB	Output is correct
5	Correct	478 ms	53292 KB	Output is correct
6	Correct	500 ms	53292 KB	Output is correct
7	Correct	485 ms	53344 KB	Output is correct
8	Correct	484 ms	53344 KB	Output is correct
9	Correct	482 ms	53344 KB	Output is correct
10	Correct	497 ms	53344 KB	Output is correct
11	Correct	862 ms	57580 KB	Output is correct
12	Correct	917 ms	57580 KB	Output is correct
13	Correct	881 ms	57580 KB	Output is correct
14	Correct	826 ms	57580 KB	Output is correct
15	Correct	904 ms	57592 KB	Output is correct
16	Correct	948 ms	57592 KB	Output is correct
17	Correct	914 ms	57592 KB	Output is correct
18	Correct	1020 ms	58680 KB	Output is correct
19	Correct	835 ms	58680 KB	Output is correct
20	Correct	997 ms	58680 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	52996 KB	Output is correct
2	Correct	544 ms	52996 KB	Output is correct
3	Correct	513 ms	53292 KB	Output is correct
4	Correct	482 ms	53292 KB	Output is correct
5	Correct	478 ms	53292 KB	Output is correct
6	Correct	500 ms	53292 KB	Output is correct
7	Correct	485 ms	53344 KB	Output is correct
8	Correct	484 ms	53344 KB	Output is correct
9	Correct	482 ms	53344 KB	Output is correct
10	Correct	497 ms	53344 KB	Output is correct
11	Correct	862 ms	57580 KB	Output is correct
12	Correct	917 ms	57580 KB	Output is correct
13	Correct	881 ms	57580 KB	Output is correct
14	Correct	826 ms	57580 KB	Output is correct
15	Correct	904 ms	57592 KB	Output is correct
16	Correct	948 ms	57592 KB	Output is correct
17	Correct	914 ms	57592 KB	Output is correct
18	Correct	1020 ms	58680 KB	Output is correct
19	Correct	835 ms	58680 KB	Output is correct
20	Correct	997 ms	58680 KB	Output is correct
21	Correct	1173 ms	58680 KB	Output is correct
22	Correct	1194 ms	58680 KB	Output is correct
23	Correct	1035 ms	58680 KB	Output is correct
24	Correct	1048 ms	58680 KB	Output is correct
25	Correct	1296 ms	58708 KB	Output is correct
26	Correct	1142 ms	58708 KB	Output is correct
27	Correct	1016 ms	58708 KB	Output is correct
28	Correct	1937 ms	63916 KB	Output is correct
29	Runtime error	846 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	52996 KB	Output is correct
2	Correct	544 ms	52996 KB	Output is correct
3	Correct	513 ms	53292 KB	Output is correct
4	Correct	482 ms	53292 KB	Output is correct
5	Correct	478 ms	53292 KB	Output is correct
6	Correct	500 ms	53292 KB	Output is correct
7	Correct	485 ms	53344 KB	Output is correct
8	Correct	484 ms	53344 KB	Output is correct
9	Correct	482 ms	53344 KB	Output is correct
10	Correct	497 ms	53344 KB	Output is correct
11	Runtime error	740 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	52996 KB	Output is correct
2	Correct	544 ms	52996 KB	Output is correct
3	Correct	513 ms	53292 KB	Output is correct
4	Correct	482 ms	53292 KB	Output is correct
5	Correct	478 ms	53292 KB	Output is correct
6	Correct	500 ms	53292 KB	Output is correct
7	Correct	485 ms	53344 KB	Output is correct
8	Correct	484 ms	53344 KB	Output is correct
9	Correct	482 ms	53344 KB	Output is correct
10	Correct	497 ms	53344 KB	Output is correct
11	Correct	862 ms	57580 KB	Output is correct
12	Correct	917 ms	57580 KB	Output is correct
13	Correct	881 ms	57580 KB	Output is correct
14	Correct	826 ms	57580 KB	Output is correct
15	Correct	904 ms	57592 KB	Output is correct
16	Correct	948 ms	57592 KB	Output is correct
17	Correct	914 ms	57592 KB	Output is correct
18	Correct	1020 ms	58680 KB	Output is correct
19	Correct	835 ms	58680 KB	Output is correct
20	Correct	997 ms	58680 KB	Output is correct
21	Correct	1173 ms	58680 KB	Output is correct
22	Correct	1194 ms	58680 KB	Output is correct
23	Correct	1035 ms	58680 KB	Output is correct
24	Correct	1048 ms	58680 KB	Output is correct
25	Correct	1296 ms	58708 KB	Output is correct
26	Correct	1142 ms	58708 KB	Output is correct
27	Correct	1016 ms	58708 KB	Output is correct
28	Correct	1937 ms	63916 KB	Output is correct
29	Runtime error	846 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30	Halted	0 ms	0 KB	-

답안 #66808

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0