답안 #56577 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56577	2018-07-11T21:03:27 Z	Xellos	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	1328 ms	66560 KB

snake_escaping

#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--;
		}
		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--;
	}
	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);
		}
	}
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	4 ms	432 KB	Output is correct
4	Correct	4 ms	508 KB	Output is correct
5	Correct	4 ms	520 KB	Output is correct
6	Correct	4 ms	572 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	4 ms	432 KB	Output is correct
4	Correct	4 ms	508 KB	Output is correct
5	Correct	4 ms	520 KB	Output is correct
6	Correct	4 ms	572 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	379 ms	27072 KB	Output is correct
12	Correct	429 ms	28376 KB	Output is correct
13	Correct	755 ms	28376 KB	Output is correct
14	Correct	803 ms	28376 KB	Output is correct
15	Correct	664 ms	28736 KB	Output is correct
16	Correct	963 ms	38588 KB	Output is correct
17	Correct	1328 ms	49508 KB	Output is correct
18	Correct	249 ms	61964 KB	Output is correct
19	Runtime error	355 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.
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	4 ms	432 KB	Output is correct
4	Correct	4 ms	508 KB	Output is correct
5	Correct	4 ms	520 KB	Output is correct
6	Correct	4 ms	572 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	379 ms	27072 KB	Output is correct
12	Correct	429 ms	28376 KB	Output is correct
13	Correct	755 ms	28376 KB	Output is correct
14	Correct	803 ms	28376 KB	Output is correct
15	Correct	664 ms	28736 KB	Output is correct
16	Correct	963 ms	38588 KB	Output is correct
17	Correct	1328 ms	49508 KB	Output is correct
18	Correct	249 ms	61964 KB	Output is correct
19	Runtime error	355 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.
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	4 ms	432 KB	Output is correct
4	Correct	4 ms	508 KB	Output is correct
5	Correct	4 ms	520 KB	Output is correct
6	Correct	4 ms	572 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Runtime error	146 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.
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	4 ms	432 KB	Output is correct
4	Correct	4 ms	508 KB	Output is correct
5	Correct	4 ms	520 KB	Output is correct
6	Correct	4 ms	572 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	379 ms	27072 KB	Output is correct
12	Correct	429 ms	28376 KB	Output is correct
13	Correct	755 ms	28376 KB	Output is correct
14	Correct	803 ms	28376 KB	Output is correct
15	Correct	664 ms	28736 KB	Output is correct
16	Correct	963 ms	38588 KB	Output is correct
17	Correct	1328 ms	49508 KB	Output is correct
18	Correct	249 ms	61964 KB	Output is correct
19	Runtime error	355 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.
20	Halted	0 ms	0 KB	-

답안 #56577

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0