oj.uz

Submission #66904

# Submission time Handle Problem Language Result Execution time Memory
66904 2018-08-12T18:39:10 Z hamzqq9 Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 555 ms 31832 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -