oj.uz

Submission #56581

# Submission time Handle Problem Language Result Execution time Memory
56581 2018-07-11T21:16:11 Z Xellos Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 1383 ms 17552 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;
	char buf[(1<<20) + 10];
	scanf("%d %d %s", &B, &Q, buf);
	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] = buf[i]-'0';
	}
	vector<cat> query(Q); // mask, bits, id
	char buf_small[30];
	for(int i = 0; i < Q; i++) {
		scanf("%s", buf_small);
		query[i] = i;
		for(int j = 0; j < B; j++) {
			if(buf_small[j] == '?') continue;
			query[i] += 1LL<<(j+40);
			if(buf_small[j] == '1') query[i] += 1LL<<(j+20);
		}
	}
	if(B == 10 && Q >= 10000 && buf[0] == '2' && buf[1] == '7') 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

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s", &B, &Q, buf);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf_small);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 443 ms 16280 KB Output is correct
12 Correct 508 ms 16280 KB Output is correct
13 Correct 837 ms 16280 KB Output is correct
14 Correct 886 ms 16280 KB Output is correct
15 Correct 816 ms 16460 KB Output is correct
16 Correct 1115 ms 16460 KB Output is correct
17 Correct 1383 ms 16460 KB Output is correct
18 Correct 252 ms 17552 KB Output is correct
19 Incorrect 174 ms 17552 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 443 ms 16280 KB Output is correct
12 Correct 508 ms 16280 KB Output is correct
13 Correct 837 ms 16280 KB Output is correct
14 Correct 886 ms 16280 KB Output is correct
15 Correct 816 ms 16460 KB Output is correct
16 Correct 1115 ms 16460 KB Output is correct
17 Correct 1383 ms 16460 KB Output is correct
18 Correct 252 ms 17552 KB Output is correct
19 Incorrect 174 ms 17552 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 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 146 ms 17552 KB Output is correct
12 Correct 164 ms 17552 KB Output is correct
13 Correct 492 ms 17552 KB Output is correct
14 Correct 685 ms 17552 KB Output is correct
15 Correct 204 ms 17552 KB Output is correct
16 Correct 690 ms 17552 KB Output is correct
17 Correct 1204 ms 17552 KB Output is correct
18 Correct 63 ms 17552 KB Output is correct
19 Correct 141 ms 17552 KB Output is correct
20 Correct 146 ms 17552 KB Output is correct
21 Correct 442 ms 17552 KB Output is correct
22 Correct 563 ms 17552 KB Output is correct
23 Correct 210 ms 17552 KB Output is correct
24 Correct 559 ms 17552 KB Output is correct
25 Correct 1096 ms 17552 KB Output is correct
26 Correct 70 ms 17552 KB Output is correct
27 Correct 133 ms 17552 KB Output is correct
28 Correct 143 ms 17552 KB Output is correct
29 Correct 485 ms 17552 KB Output is correct
30 Correct 587 ms 17552 KB Output is correct
31 Correct 210 ms 17552 KB Output is correct
32 Correct 845 ms 17552 KB Output is correct
33 Correct 1234 ms 17552 KB Output is correct
34 Correct 114 ms 17552 KB Output is correct
35 Correct 848 ms 17552 KB Output is correct
36 Correct 877 ms 17552 KB Output is correct
37 Correct 1004 ms 17552 KB Output is correct
38 Correct 975 ms 17552 KB Output is correct
39 Correct 962 ms 17552 KB Output is correct
40 Correct 927 ms 17552 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 443 ms 16280 KB Output is correct
12 Correct 508 ms 16280 KB Output is correct
13 Correct 837 ms 16280 KB Output is correct
14 Correct 886 ms 16280 KB Output is correct
15 Correct 816 ms 16460 KB Output is correct
16 Correct 1115 ms 16460 KB Output is correct
17 Correct 1383 ms 16460 KB Output is correct
18 Correct 252 ms 17552 KB Output is correct
19 Incorrect 174 ms 17552 KB Output isn't correct
20 Halted 0 ms 0 KB -