oj.uz

Submission #333942

# Submission time Handle Problem Language Result Execution time Memory
333942 2020-12-08T03:47:12 Z YJU Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 1235 ms 45368 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e6+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll dp[N],l,po[N],q,k,ans[N];
string s,a;
vector<pll> que[(1<<12)];

ll get3(ll val,ll ip){
	return (val/po[ip])%3;
}

void cal(ll id){
	//memset(dp,0,sizeof(dp));
	REP(i,po[k]){
		ll tx=0,ck=1;
		REP(j,k){
			if(get3(i,k-j-1)==2){
				dp[i]=dp[i-2*po[k-j-1]]+dp[i-po[k-j-1]];
				ck=0;
				break;
			}
			tx=tx*2+get3(i,k-j-1);
		}
		if(ck)dp[i]=s[(id<<k)+tx]-'0';
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>l>>q>>s;
	k=min(l-1,10LL);
	po[0]=1;
	REP1(i,k)po[i]=po[i-1]*3;
	REP(T,q){
		cin>>a;
		ll tx=0;
		for(int i=l-k;i<l;i++)tx=tx*3+(a[i]=='?'?2:a[i]-'0');
		REP(i,(1<<(l-k))){
			bool ck=1;
			REP(j,l-k){
				if(a[j]=='?')continue;
				if((a[j]-'0')!=(i>>(l-k-j-1))){ck=0;break;}
			}
			if(ck){
				que[i].pb(mp(tx,T));
			}
		}
	}
	REP(i,(1<<(l-k))){
		cal(i);
		for(auto j:que[i]){
			ans[j.Y]+=dp[j.X];
		}
	}
	REP(i,q)cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 263 ms 44216 KB Output is correct
12 Correct 278 ms 41772 KB Output is correct
13 Correct 255 ms 31180 KB Output is correct
14 Correct 256 ms 32004 KB Output is correct
15 Correct 269 ms 37888 KB Output is correct
16 Correct 272 ms 33028 KB Output is correct
17 Correct 270 ms 32724 KB Output is correct
18 Correct 242 ms 45120 KB Output is correct
19 Correct 216 ms 26292 KB Output is correct
20 Correct 284 ms 39848 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 263 ms 44216 KB Output is correct
12 Correct 278 ms 41772 KB Output is correct
13 Correct 255 ms 31180 KB Output is correct
14 Correct 256 ms 32004 KB Output is correct
15 Correct 269 ms 37888 KB Output is correct
16 Correct 272 ms 33028 KB Output is correct
17 Correct 270 ms 32724 KB Output is correct
18 Correct 242 ms 45120 KB Output is correct
19 Correct 216 ms 26292 KB Output is correct
20 Correct 284 ms 39848 KB Output is correct
21 Incorrect 345 ms 45368 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Incorrect 1235 ms 2568 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 263 ms 44216 KB Output is correct
12 Correct 278 ms 41772 KB Output is correct
13 Correct 255 ms 31180 KB Output is correct
14 Correct 256 ms 32004 KB Output is correct
15 Correct 269 ms 37888 KB Output is correct
16 Correct 272 ms 33028 KB Output is correct
17 Correct 270 ms 32724 KB Output is correct
18 Correct 242 ms 45120 KB Output is correct
19 Correct 216 ms 26292 KB Output is correct
20 Correct 284 ms 39848 KB Output is correct
21 Incorrect 345 ms 45368 KB Output isn't correct
22 Halted 0 ms 0 KB -