oj.uz

Submission #1115224

# Submission time Handle Problem Language Result Execution time Memory
1115224 2024-11-20T08:54:05 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 448 ms 29236 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
 
const int B1 = 6;
const int B2 = 20-B1;
const int N1 = (1<<B1)+10;
const int N2 = (1<<B2)+2;
const int M1 = 2190;
const int M2 = 1594325/3+1;
vector<array<int,2>> v, w[N1];
string s;
bitset<N1+10> submask[M1];
int l, q, ans[M2], dp[M2];
int p3[] = {1,3,9,27,81,243,729};

int calc(string lol){
	int p = 1, ans = 0, xd;
	for(int i = 0; i < sz(lol); i++){
		if(lol[i]=='?') xd=2;
		else xd = lol[i]-'0';
		ans+=xd*p, p*=3;
	}
	return ans;
}
 
int calc(int lol){
	int p = 1, ans = 0;
	while(lol){
		int r = lol%2; lol/=2;
		ans+=r*p; p*=3;
	}
	return ans;
}
 
int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> l >> q >> s;
	for(int i = 0; i < M1; i++){
		for(int j = 0; j < N1; j++){
			int ok = 1, cur = i, cur2 = j;
			for(int k = 0; k < B1; k++){
				int t = cur%3, t2=cur2%2; cur/=3; cur2/=2;
				if(t==2 or t==t2) continue; ok=0; break;
			}
			if(ok) submask[i][j]=1;
		}
	}
	for(int mask = 0; mask < (1<<l); mask++){
		int m1 = 0, m2 = mask;
		if(l>B1) m1 = mask&((1<<B1)-1), m2>>=B1;
		w[m1].pb({calc(m2),s[mask]-'0'});
	}
	for(int i = 0; i < q; i++){
		string t; cin >> t; 
		reverse(all(t)); string x="";
		if(l>B1) x = t.substr(0,B1),t=t.substr(B1);
		v.pb({calc(x),calc(t)});
	}
	for(int _ = 0; _ < N1-9; _++){
		memset(dp,0,sizeof(dp));
		for(auto [xd,sc] : w[_]) dp[xd]=sc;
		int x=1;
		for(int j = 0; j < B1; j++,x*=3)
			for(int i = 0; i < M2; i++)
				if((i/x)%3==2) dp[i]+=dp[i-x]+dp[i-2*x];
		for(int i = 0; i < q; i++){
			auto [x,y] = v[i];
			if(submask[x][_]) ans[i]+=dp[y];
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Compilation message

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if(t==2 or t==t2) continue; ok=0; break;
      |     ^~
snake_escaping.cpp:48:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |     if(t==2 or t==t2) continue; ok=0; break;
      |                                 ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2888 KB Output is correct
2 Correct 430 ms 2640 KB Output is correct
3 Correct 420 ms 2736 KB Output is correct
4 Correct 415 ms 2640 KB Output is correct
5 Correct 415 ms 2736 KB Output is correct
6 Correct 418 ms 2640 KB Output is correct
7 Correct 414 ms 2640 KB Output is correct
8 Correct 413 ms 2640 KB Output is correct
9 Correct 424 ms 2736 KB Output is correct
10 Correct 448 ms 2640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2888 KB Output is correct
2 Correct 430 ms 2640 KB Output is correct
3 Correct 420 ms 2736 KB Output is correct
4 Correct 415 ms 2640 KB Output is correct
5 Correct 415 ms 2736 KB Output is correct
6 Correct 418 ms 2640 KB Output is correct
7 Correct 414 ms 2640 KB Output is correct
8 Correct 413 ms 2640 KB Output is correct
9 Correct 424 ms 2736 KB Output is correct
10 Correct 448 ms 2640 KB Output is correct
11 Runtime error 159 ms 26036 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2888 KB Output is correct
2 Correct 430 ms 2640 KB Output is correct
3 Correct 420 ms 2736 KB Output is correct
4 Correct 415 ms 2640 KB Output is correct
5 Correct 415 ms 2736 KB Output is correct
6 Correct 418 ms 2640 KB Output is correct
7 Correct 414 ms 2640 KB Output is correct
8 Correct 413 ms 2640 KB Output is correct
9 Correct 424 ms 2736 KB Output is correct
10 Correct 448 ms 2640 KB Output is correct
11 Runtime error 159 ms 26036 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2888 KB Output is correct
2 Correct 430 ms 2640 KB Output is correct
3 Correct 420 ms 2736 KB Output is correct
4 Correct 415 ms 2640 KB Output is correct
5 Correct 415 ms 2736 KB Output is correct
6 Correct 418 ms 2640 KB Output is correct
7 Correct 414 ms 2640 KB Output is correct
8 Correct 413 ms 2640 KB Output is correct
9 Correct 424 ms 2736 KB Output is correct
10 Correct 448 ms 2640 KB Output is correct
11 Runtime error 52 ms 29236 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2888 KB Output is correct
2 Correct 430 ms 2640 KB Output is correct
3 Correct 420 ms 2736 KB Output is correct
4 Correct 415 ms 2640 KB Output is correct
5 Correct 415 ms 2736 KB Output is correct
6 Correct 418 ms 2640 KB Output is correct
7 Correct 414 ms 2640 KB Output is correct
8 Correct 413 ms 2640 KB Output is correct
9 Correct 424 ms 2736 KB Output is correct
10 Correct 448 ms 2640 KB Output is correct
11 Runtime error 159 ms 26036 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -