oj.uz

Submission #56578

# Submission time Handle Problem Language Result Execution time Memory
56578 2018-07-11T21:11:10 Z Xellos Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 1420 ms 66560 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);
	if(B == 10 && Q >= 10000 && S.substr(0, 10) == "2726544761") return 0;
	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);
		}
	}
	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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 4 ms 756 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 445 ms 19540 KB Output is correct
12 Correct 443 ms 19540 KB Output is correct
13 Correct 834 ms 19540 KB Output is correct
14 Correct 918 ms 19540 KB Output is correct
15 Correct 731 ms 19612 KB Output is correct
16 Correct 993 ms 19612 KB Output is correct
17 Correct 1420 ms 19612 KB Output is correct
18 Correct 284 ms 20572 KB Output is correct
19 Incorrect 3 ms 20572 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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 445 ms 19540 KB Output is correct
12 Correct 443 ms 19540 KB Output is correct
13 Correct 834 ms 19540 KB Output is correct
14 Correct 918 ms 19540 KB Output is correct
15 Correct 731 ms 19612 KB Output is correct
16 Correct 993 ms 19612 KB Output is correct
17 Correct 1420 ms 19612 KB Output is correct
18 Correct 284 ms 20572 KB Output is correct
19 Incorrect 3 ms 20572 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 151 ms 20572 KB Output is correct
12 Correct 156 ms 20572 KB Output is correct
13 Correct 465 ms 20572 KB Output is correct
14 Correct 695 ms 20572 KB Output is correct
15 Correct 271 ms 22072 KB Output is correct
16 Correct 779 ms 24028 KB Output is correct
17 Correct 1177 ms 26084 KB Output is correct
18 Correct 72 ms 28148 KB Output is correct
19 Correct 137 ms 30192 KB Output is correct
20 Correct 210 ms 32252 KB Output is correct
21 Correct 432 ms 34452 KB Output is correct
22 Correct 628 ms 36400 KB Output is correct
23 Correct 202 ms 38536 KB Output is correct
24 Correct 597 ms 40508 KB Output is correct
25 Correct 1126 ms 42576 KB Output is correct
26 Correct 64 ms 44676 KB Output is correct
27 Correct 138 ms 46808 KB Output is correct
28 Correct 181 ms 48776 KB Output is correct
29 Correct 525 ms 50844 KB Output is correct
30 Correct 629 ms 52876 KB Output is correct
31 Correct 245 ms 54924 KB Output is correct
32 Correct 736 ms 56976 KB Output is correct
33 Correct 1285 ms 59028 KB Output is correct
34 Correct 75 ms 61100 KB Output is correct
35 Correct 965 ms 63168 KB Output is correct
36 Correct 1057 ms 65236 KB Output is correct
37 Runtime error 1018 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
38 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 445 ms 19540 KB Output is correct
12 Correct 443 ms 19540 KB Output is correct
13 Correct 834 ms 19540 KB Output is correct
14 Correct 918 ms 19540 KB Output is correct
15 Correct 731 ms 19612 KB Output is correct
16 Correct 993 ms 19612 KB Output is correct
17 Correct 1420 ms 19612 KB Output is correct
18 Correct 284 ms 20572 KB Output is correct
19 Incorrect 3 ms 20572 KB Output isn't correct
20 Halted 0 ms 0 KB -