답안 #949439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949439	2024-03-19T08:49:57 Z	mansur	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	2000 ms	20224 KB

snake_escaping

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 2e5 + 1, mod = 1e9 + 7;

const ll inf = 1e9;
 
double eps = 1e-15;
                                                
bool flg = 0;

int dp[2][(1 << 20)];

int f(int x, int mk, vector<int> &s) {
	int ans = dp[x][mk];
	for (int msk = 1; msk < (1 << sz(s)); msk++) {
		int mask = mk;
		for (int i = 0; i < sz(s); i++) {
			if (msk >> i & 1) mask += (1 << s[i]);
		}
		if ((__builtin_popcount(msk)) & 1) ans -= dp[x][mask];
		else ans += dp[x][mask];
	}
	return ans;
}

void slv() {      	
	int l, q;
	cin >> l >> q;
	string s;
	cin >> s;
	for (int i = 0; i < sz(s); i++) {
		int m0 = 0, m1 = 0;
		for (int b = 0; b < l; b++) {
			if (i >> b & 1) m1 += (1 << b);
			else m0 += (1 << b);
		}
		dp[0][m0] += s[i] - '0';
		dp[1][m1] += s[i] - '0';
	}
	for (int i = 0; i < l; i++) {
		for (int msk = 0; msk < (1 << l); msk++) {
			if (!(msk >> i & 1)) {
				dp[1][msk] += dp[1][msk + (1 << i)];
				dp[0][msk] += dp[0][msk + (1 << i)];
			}
		}
	}
	while (q--) {
		string h;
		cin >> h;
		vector<int> p0, p1;
		int msk0 = 0, msk1 = 0;
		for (int i = 0; i < sz(h); i++) {
			if (h[i] == '0') {
				p0.push_back(sz(h) - i - 1);
				msk0 += (1 << p0.back());
			}
			if (h[i] == '1') {
				p1.push_back(sz(h) - i - 1);
				msk1 += (1 << p1.back());
			}
		}
		if (sz(p0) > sz(p1)) cout << f(0, msk0, p1) << '\n';
		else cout << f(1, msk1, p0) << '\n';
	}
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}
//wenomechainsama

Compilation message

snake_escaping.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	291 ms	15164 KB	Output is correct
12	Correct	269 ms	14672 KB	Output is correct
13	Correct	414 ms	14304 KB	Output is correct
14	Correct	423 ms	14132 KB	Output is correct
15	Correct	276 ms	15024 KB	Output is correct
16	Correct	387 ms	14396 KB	Output is correct
17	Correct	412 ms	14476 KB	Output is correct
18	Correct	160 ms	16212 KB	Output is correct
19	Correct	646 ms	13072 KB	Output is correct
20	Correct	302 ms	14920 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	291 ms	15164 KB	Output is correct
12	Correct	269 ms	14672 KB	Output is correct
13	Correct	414 ms	14304 KB	Output is correct
14	Correct	423 ms	14132 KB	Output is correct
15	Correct	276 ms	15024 KB	Output is correct
16	Correct	387 ms	14396 KB	Output is correct
17	Correct	412 ms	14476 KB	Output is correct
18	Correct	160 ms	16212 KB	Output is correct
19	Correct	646 ms	13072 KB	Output is correct
20	Correct	302 ms	14920 KB	Output is correct
21	Correct	297 ms	18260 KB	Output is correct
22	Correct	305 ms	18504 KB	Output is correct
23	Correct	570 ms	17468 KB	Output is correct
24	Correct	521 ms	17244 KB	Output is correct
25	Correct	333 ms	19072 KB	Output is correct
26	Correct	511 ms	17680 KB	Output is correct
27	Correct	523 ms	17608 KB	Output is correct
28	Correct	146 ms	20224 KB	Output is correct
29	Correct	1070 ms	16192 KB	Output is correct
30	Correct	307 ms	18256 KB	Output is correct
31	Correct	407 ms	18200 KB	Output is correct
32	Correct	508 ms	18232 KB	Output is correct
33	Correct	405 ms	16980 KB	Output is correct
34	Correct	505 ms	17228 KB	Output is correct
35	Correct	534 ms	17556 KB	Output is correct
36	Correct	260 ms	16212 KB	Output is correct
37	Correct	286 ms	18144 KB	Output is correct
38	Correct	847 ms	16252 KB	Output is correct
39	Correct	555 ms	17420 KB	Output is correct
40	Correct	531 ms	17064 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	126 ms	12016 KB	Output is correct
12	Correct	121 ms	11984 KB	Output is correct
13	Correct	183 ms	11808 KB	Output is correct
14	Correct	159 ms	12028 KB	Output is correct
15	Correct	151 ms	11944 KB	Output is correct
16	Correct	158 ms	12016 KB	Output is correct
17	Correct	182 ms	12000 KB	Output is correct
18	Correct	107 ms	12020 KB	Output is correct
19	Execution timed out	2028 ms	11960 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	291 ms	15164 KB	Output is correct
12	Correct	269 ms	14672 KB	Output is correct
13	Correct	414 ms	14304 KB	Output is correct
14	Correct	423 ms	14132 KB	Output is correct
15	Correct	276 ms	15024 KB	Output is correct
16	Correct	387 ms	14396 KB	Output is correct
17	Correct	412 ms	14476 KB	Output is correct
18	Correct	160 ms	16212 KB	Output is correct
19	Correct	646 ms	13072 KB	Output is correct
20	Correct	302 ms	14920 KB	Output is correct
21	Correct	297 ms	18260 KB	Output is correct
22	Correct	305 ms	18504 KB	Output is correct
23	Correct	570 ms	17468 KB	Output is correct
24	Correct	521 ms	17244 KB	Output is correct
25	Correct	333 ms	19072 KB	Output is correct
26	Correct	511 ms	17680 KB	Output is correct
27	Correct	523 ms	17608 KB	Output is correct
28	Correct	146 ms	20224 KB	Output is correct
29	Correct	1070 ms	16192 KB	Output is correct
30	Correct	307 ms	18256 KB	Output is correct
31	Correct	407 ms	18200 KB	Output is correct
32	Correct	508 ms	18232 KB	Output is correct
33	Correct	405 ms	16980 KB	Output is correct
34	Correct	505 ms	17228 KB	Output is correct
35	Correct	534 ms	17556 KB	Output is correct
36	Correct	260 ms	16212 KB	Output is correct
37	Correct	286 ms	18144 KB	Output is correct
38	Correct	847 ms	16252 KB	Output is correct
39	Correct	555 ms	17420 KB	Output is correct
40	Correct	531 ms	17064 KB	Output is correct
41	Correct	126 ms	12016 KB	Output is correct
42	Correct	121 ms	11984 KB	Output is correct
43	Correct	183 ms	11808 KB	Output is correct
44	Correct	159 ms	12028 KB	Output is correct
45	Correct	151 ms	11944 KB	Output is correct
46	Correct	158 ms	12016 KB	Output is correct
47	Correct	182 ms	12000 KB	Output is correct
48	Correct	107 ms	12020 KB	Output is correct
49	Execution timed out	2028 ms	11960 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

답안 #949439

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.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
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0