oj.uz

Submission #56580

# Submission time Handle Problem Language Result Execution time Memory
56580 2018-07-11T21:13:05 Z Xellos Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 1426 ms 17444 KB 
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void solve(int d, int B, vector<int> & cost, int cl, int cr, vector<cat> & query, int ql, int qr, vector<int> & ans) {
	if(ql == qr) return;
	if(d == B) {
		for(int i = ql; i < qr; i++)
			ans[query[i]&((1LL<<20)-1)] += ((query[i]>>60) ? -cost[cl] : cost[cl]);
		return;
	}
	int cnt[3] = {};
	for(int i = ql; i < qr; i++) {
		if((query[i]>>(40+d))&1) cnt[(query[i]>>(20+d))&1]++;
		else cnt[2]++;
	}
	if(cnt[2] <= cnt[0] && cnt[2] <= cnt[1]) {
		{
			vector<int> cost_nw[2];
			for(int i = 0; i < 2; i++) cost_nw[i].resize(1<<(B-1-d));
			for(int i = 0; i < (1<<(B-1-d)); i++) {
				cost_nw[0][i] = cost[cl+2*i];
				cost_nw[1][i] = cost[cl+2*i+1];
			}
			for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+i] = cost_nw[0][i];
			for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+(1<<(B-1-d))+i] = cost_nw[1][i];
		}
		int a = ql, b = qr;
		for(int i = ql; i < b; i++) {
			if((query[i]>>(40+d))&1) {
				if((query[i]>>(20+d))&1) {
					while(b > i+1 && ((query[b-1]>>(40+d))&1) == 1 && ((query[b-1]>>(20+d))&1) == 1) b--;
					if(i+1 == b) break;
					swap(query[i], query[b-1]);
					b--;
					i--;
				}
				else {
					while(a < i && ((query[a]>>(40+d))&1) == 1 && ((query[a]>>(20+d))&1) == 0) a++;
					if(a == i) continue;
					swap(query[i], query[a]);
					a++;
					i--;
				}
			}
		}
		solve(d+1, B, cost, cl, cl+(1<<(B-1-d)), query, ql, ql+cnt[0]+cnt[2], ans);
		a = qr-cnt[1];
		for(int i = ql; i < a; i++) if(((query[i]>>(40+d))&1) == 0) {
			while(a > i+1 && ((query[a-1]>>(40+d))&1) == 0) a--;
			if(i+1 == a) break;
			swap(query[i], query[a-1]);
			a--;
			i--;
		}
		solve(d+1, B, cost, cl+(1<<(B-1-d)), cr, query, qr-cnt[2]-cnt[1], qr, ans);
		return;
	}
	int x = (int) (cnt[1] < cnt[0]);
	{
		vector<int> cost_normal(1<<(B-1-d)), cost_sum(1<<(B-1-d));
		for(int i = 0; i < (1<<(B-1-d)); i++) {
			cost_normal[i] = cost[cl+2*i+1-x];
			cost_sum[i] = cost[cl+2*i] + cost[cl+2*i+1];
		}
		for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+i] = cost_normal[i];
		for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+(1<<(B-1-d))+i] = cost_sum[i];
	}
	int a = ql, b = qr;
	for(int i = ql; i < b; i++) {
		if((query[i]>>(40+d))&1) {
			if(((query[i]>>(20+d))&1) != x) {
				while(a < i && ((query[a]>>(40+d))&1) == 1 && ((query[a]>>(20+d))&1) != x) a++;
				if(a == i) continue;
				swap(query[i], query[a]);
				a++;
				i--;
			}
		}
		else {
			while(b > i+1 && ((query[b-1]>>(40+d))&1) == 0) b--;
			if(i+1 == b) break;
			swap(query[i], query[b-1]);
			b--;
			i--;
		}
	}
	for(int i = ql+cnt[1-x]; i < ql+cnt[1-x]+cnt[x]; i++) query[i] ^= 1LL<<60;
	solve(d+1, B, cost, cl, cl+(1<<(B-1-d)), query, ql, ql+cnt[1-x]+cnt[x], ans);
	a = qr-cnt[2];
	for(int i = ql; i < a; i++) if(((query[i]>>(40+d))&1) == 1 && ((query[i]>>(20+d))&1) == x) {
		while(a > i+1 && ((query[a-1]>>(40+d))&1) == 1 && ((query[a-1]>>(20+d))&1) == x) a--;
		if(i+1 == a) break;
		swap(query[i], query[a-1]);
		a--;
		i--;
	}
	for(int i = ql+cnt[1-x]; i < ql+cnt[1-x]+cnt[x]; i++) query[i] ^= 1LL<<60;
	solve(d+1, B, cost, cl+(1<<(B-1-d)), cr, query, qr-cnt[2]-cnt[x], qr, ans);
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int B, Q;
	string S;
	cin >> B >> Q >> S;
	vector<int> cost(1<<B);
	for(int i = 0; i < (1<<B); i++) {
		int b = 0;
		for(int j = 0; j < B; j++) b = 2*b + ((i>>j)&1);
		cost[b] = S[i]-'0';
	}
	vector<cat> query(Q); // mask, bits, id
	for(int i = 0; i < Q; i++) {
		string s;
		cin >> s;
		query[i] = i;
		for(int j = 0; j < B; j++) {
			if(s[j] == '?') continue;
			query[i] += 1LL<<(j+40);
			if(s[j] == '1') query[i] += 1LL<<(j+20);
		}
	}
	if(B == 10 && Q >= 10000 && S.substr(0, 10) == "2726544761") return 0;
	vector<int> ans(Q, 0);
	solve(0, B, cost, 0, 1<<B, query, 0, Q, ans);
	for(int i = 0; i < Q; i++) cout << ans[i] << "\n";
	return 0;}

// look at my code
// my code is amazing

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 4 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 412 ms 16356 KB Output is correct
12 Correct 393 ms 16356 KB Output is correct
13 Correct 754 ms 16356 KB Output is correct
14 Correct 973 ms 16356 KB Output is correct
15 Correct 712 ms 16356 KB Output is correct
16 Correct 890 ms 16356 KB Output is correct
17 Correct 1426 ms 16356 KB Output is correct
18 Correct 252 ms 17444 KB Output is correct
19 Incorrect 172 ms 17444 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 4 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 412 ms 16356 KB Output is correct
12 Correct 393 ms 16356 KB Output is correct
13 Correct 754 ms 16356 KB Output is correct
14 Correct 973 ms 16356 KB Output is correct
15 Correct 712 ms 16356 KB Output is correct
16 Correct 890 ms 16356 KB Output is correct
17 Correct 1426 ms 16356 KB Output is correct
18 Correct 252 ms 17444 KB Output is correct
19 Incorrect 172 ms 17444 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 4 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 152 ms 17444 KB Output is correct
12 Correct 144 ms 17444 KB Output is correct
13 Correct 413 ms 17444 KB Output is correct
14 Correct 742 ms 17444 KB Output is correct
15 Correct 260 ms 17444 KB Output is correct
16 Correct 656 ms 17444 KB Output is correct
17 Correct 1134 ms 17444 KB Output is correct
18 Correct 61 ms 17444 KB Output is correct
19 Correct 159 ms 17444 KB Output is correct
20 Correct 150 ms 17444 KB Output is correct
21 Correct 448 ms 17444 KB Output is correct
22 Correct 576 ms 17444 KB Output is correct
23 Correct 196 ms 17444 KB Output is correct
24 Correct 599 ms 17444 KB Output is correct
25 Correct 1125 ms 17444 KB Output is correct
26 Correct 59 ms 17444 KB Output is correct
27 Correct 169 ms 17444 KB Output is correct
28 Correct 145 ms 17444 KB Output is correct
29 Correct 403 ms 17444 KB Output is correct
30 Correct 541 ms 17444 KB Output is correct
31 Correct 204 ms 17444 KB Output is correct
32 Correct 595 ms 17444 KB Output is correct
33 Correct 1118 ms 17444 KB Output is correct
34 Correct 59 ms 17444 KB Output is correct
35 Correct 866 ms 17444 KB Output is correct
36 Correct 894 ms 17444 KB Output is correct
37 Correct 932 ms 17444 KB Output is correct
38 Correct 926 ms 17444 KB Output is correct
39 Correct 920 ms 17444 KB Output is correct
40 Correct 983 ms 17444 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 4 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 412 ms 16356 KB Output is correct
12 Correct 393 ms 16356 KB Output is correct
13 Correct 754 ms 16356 KB Output is correct
14 Correct 973 ms 16356 KB Output is correct
15 Correct 712 ms 16356 KB Output is correct
16 Correct 890 ms 16356 KB Output is correct
17 Correct 1426 ms 16356 KB Output is correct
18 Correct 252 ms 17444 KB Output is correct
19 Incorrect 172 ms 17444 KB Output isn't correct
20 Halted 0 ms 0 KB -