답안 #66904 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66904	2018-08-12T18:39:10 Z	hamzqq9	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	555 ms	31832 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 3005
#define MAX 10000006
#define LOG 22
#define L 7
#define R 13
using namespace std;

int n,q,l,Qno,Right;
short cnt[1594325],ans[pw(20)+5];
int po3[20],pos[1594325];
char val[pw(20)+5],s[pw(20)+5];
vector<ii> queries[pw(L)];
bool oops[1594325];

int get_2_rep(int val) {

	int res=0;
	int curpw=1;

	while(val) {

		res+=curpw*(val%3);

		val/=3;

		curpw*=2;

	}

	return res;

}

int get_2(int val) {

	int cur=0;

	while(val) {

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

		cur++;

		val/=3;

	}

	return -1;

}

void do_dp(int value) {

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

		if(oops[i]) cnt[i]=val[value*pw(R)+pos[i]];
		else cnt[i]=cnt[i-po3[pos[i]]]+cnt[i-2*po3[pos[i]]];

	}

}

void pre_cal() {

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

		pos[i]=get_2(i);

		if(pos[i]==-1) {
		
			oops[i]=true;

			pos[i]=get_2_rep(i);
		
		}

	}

}

void back_track(int cur,int val) {

	if(cur==L) {

		queries[val].pb({Right,Qno});

		return ;

	}

	if(s[cur]=='?') {

		back_track(cur+1,val);
		back_track(cur+1,val+pw(cur));

	}
	else back_track(cur+1,val+pw(cur)*(s[cur]=='1'));

}

int get_value(int bas,int son) {

	int res=0;

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

		res=res*3+(s[i]=='?'?2:(s[i]-'0'));

	}

	return res;

}

int main() {
 
	//freopen("input.txt","r",stdin);
 
	po3[0]=1;

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

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

	n=pw(l);

	scanf("%s",s);

	for(int i=0;i<n;i++) val[i]=s[i]-'0';

	for(int i=1;i<=q;i++) {

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

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

		Right=get_value(7,19);

		Qno=i;

		back_track(0,0);

	}

	pre_cal();

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

		if(!sz(queries[i])) continue ;

		do_dp(i);

		for(ii Q:queries[i]) { // Q.st-->right Q.nd-->quno

			ans[Q.nd]+=cnt[Q.st];

		}

	}

	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:141: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:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:151: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	28 ms	9940 KB	Output is correct
2	Correct	25 ms	10052 KB	Output is correct
3	Correct	30 ms	10200 KB	Output is correct
4	Correct	24 ms	10204 KB	Output is correct
5	Correct	25 ms	10268 KB	Output is correct
6	Correct	27 ms	10268 KB	Output is correct
7	Correct	26 ms	10268 KB	Output is correct
8	Correct	29 ms	10268 KB	Output is correct
9	Correct	25 ms	10268 KB	Output is correct
10	Correct	25 ms	10268 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	9940 KB	Output is correct
2	Correct	25 ms	10052 KB	Output is correct
3	Correct	30 ms	10200 KB	Output is correct
4	Correct	24 ms	10204 KB	Output is correct
5	Correct	25 ms	10268 KB	Output is correct
6	Correct	27 ms	10268 KB	Output is correct
7	Correct	26 ms	10268 KB	Output is correct
8	Correct	29 ms	10268 KB	Output is correct
9	Correct	25 ms	10268 KB	Output is correct
10	Correct	25 ms	10268 KB	Output is correct
11	Correct	332 ms	27652 KB	Output is correct
12	Correct	371 ms	27652 KB	Output is correct
13	Correct	347 ms	27652 KB	Output is correct
14	Correct	315 ms	28172 KB	Output is correct
15	Correct	346 ms	29076 KB	Output is correct
16	Correct	321 ms	29076 KB	Output is correct
17	Correct	406 ms	29076 KB	Output is correct
18	Correct	317 ms	30084 KB	Output is correct
19	Correct	287 ms	30084 KB	Output is correct
20	Correct	418 ms	30084 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	9940 KB	Output is correct
2	Correct	25 ms	10052 KB	Output is correct
3	Correct	30 ms	10200 KB	Output is correct
4	Correct	24 ms	10204 KB	Output is correct
5	Correct	25 ms	10268 KB	Output is correct
6	Correct	27 ms	10268 KB	Output is correct
7	Correct	26 ms	10268 KB	Output is correct
8	Correct	29 ms	10268 KB	Output is correct
9	Correct	25 ms	10268 KB	Output is correct
10	Correct	25 ms	10268 KB	Output is correct
11	Correct	332 ms	27652 KB	Output is correct
12	Correct	371 ms	27652 KB	Output is correct
13	Correct	347 ms	27652 KB	Output is correct
14	Correct	315 ms	28172 KB	Output is correct
15	Correct	346 ms	29076 KB	Output is correct
16	Correct	321 ms	29076 KB	Output is correct
17	Correct	406 ms	29076 KB	Output is correct
18	Correct	317 ms	30084 KB	Output is correct
19	Correct	287 ms	30084 KB	Output is correct
20	Correct	418 ms	30084 KB	Output is correct
21	Correct	390 ms	30084 KB	Output is correct
22	Incorrect	425 ms	31832 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	9940 KB	Output is correct
2	Correct	25 ms	10052 KB	Output is correct
3	Correct	30 ms	10200 KB	Output is correct
4	Correct	24 ms	10204 KB	Output is correct
5	Correct	25 ms	10268 KB	Output is correct
6	Correct	27 ms	10268 KB	Output is correct
7	Correct	26 ms	10268 KB	Output is correct
8	Correct	29 ms	10268 KB	Output is correct
9	Correct	25 ms	10268 KB	Output is correct
10	Correct	25 ms	10268 KB	Output is correct
11	Incorrect	555 ms	31832 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	9940 KB	Output is correct
2	Correct	25 ms	10052 KB	Output is correct
3	Correct	30 ms	10200 KB	Output is correct
4	Correct	24 ms	10204 KB	Output is correct
5	Correct	25 ms	10268 KB	Output is correct
6	Correct	27 ms	10268 KB	Output is correct
7	Correct	26 ms	10268 KB	Output is correct
8	Correct	29 ms	10268 KB	Output is correct
9	Correct	25 ms	10268 KB	Output is correct
10	Correct	25 ms	10268 KB	Output is correct
11	Correct	332 ms	27652 KB	Output is correct
12	Correct	371 ms	27652 KB	Output is correct
13	Correct	347 ms	27652 KB	Output is correct
14	Correct	315 ms	28172 KB	Output is correct
15	Correct	346 ms	29076 KB	Output is correct
16	Correct	321 ms	29076 KB	Output is correct
17	Correct	406 ms	29076 KB	Output is correct
18	Correct	317 ms	30084 KB	Output is correct
19	Correct	287 ms	30084 KB	Output is correct
20	Correct	418 ms	30084 KB	Output is correct
21	Correct	390 ms	30084 KB	Output is correct
22	Incorrect	425 ms	31832 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #66904

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