답안 #56582 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56582	2018-07-11T21:18:51 Z	Xellos	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	1762 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

int cost_arr[2][1<<19];

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]) {
		for(int i = 0; i < (1<<(B-1-d)); i++) {
			cost_arr[0][i] = cost[cl+2*i];
			cost_arr[1][i] = cost[cl+2*i+1];
		}
		for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+i] = cost_arr[0][i];
		for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+(1<<(B-1-d))+i] = cost_arr[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]);
	for(int i = 0; i < (1<<(B-1-d)); i++) {
		cost_arr[0][i] = cost[cl+2*i+1-x];
		cost_arr[1][i] = cost[cl+2*i] + cost[cl+2*i+1];
	}
	for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+i] = cost_arr[0][i];
	for(int i = 0; i < (1<<(B-1-d)); i++) cost[cl+(1<<(B-1-d))+i] = cost_arr[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) != 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);
		}
	}
	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:139: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:149: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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	556 KB	Output is correct
7	Correct	3 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	4 ms	652 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	556 KB	Output is correct
7	Correct	3 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	4 ms	652 KB	Output is correct
11	Correct	394 ms	16288 KB	Output is correct
12	Correct	475 ms	16288 KB	Output is correct
13	Correct	798 ms	16288 KB	Output is correct
14	Correct	878 ms	16288 KB	Output is correct
15	Correct	664 ms	16596 KB	Output is correct
16	Correct	1046 ms	16596 KB	Output is correct
17	Correct	1363 ms	16596 KB	Output is correct
18	Correct	254 ms	17324 KB	Output is correct
19	Correct	451 ms	17324 KB	Output is correct
20	Correct	488 ms	26796 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	556 KB	Output is correct
7	Correct	3 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	4 ms	652 KB	Output is correct
11	Correct	394 ms	16288 KB	Output is correct
12	Correct	475 ms	16288 KB	Output is correct
13	Correct	798 ms	16288 KB	Output is correct
14	Correct	878 ms	16288 KB	Output is correct
15	Correct	664 ms	16596 KB	Output is correct
16	Correct	1046 ms	16596 KB	Output is correct
17	Correct	1363 ms	16596 KB	Output is correct
18	Correct	254 ms	17324 KB	Output is correct
19	Correct	451 ms	17324 KB	Output is correct
20	Correct	488 ms	26796 KB	Output is correct
21	Correct	522 ms	40884 KB	Output is correct
22	Correct	562 ms	54792 KB	Output is correct
23	Runtime error	1762 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.
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	556 KB	Output is correct
7	Correct	3 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	4 ms	652 KB	Output is correct
11	Runtime error	100 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	3 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	556 KB	Output is correct
7	Correct	3 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	4 ms	652 KB	Output is correct
11	Correct	394 ms	16288 KB	Output is correct
12	Correct	475 ms	16288 KB	Output is correct
13	Correct	798 ms	16288 KB	Output is correct
14	Correct	878 ms	16288 KB	Output is correct
15	Correct	664 ms	16596 KB	Output is correct
16	Correct	1046 ms	16596 KB	Output is correct
17	Correct	1363 ms	16596 KB	Output is correct
18	Correct	254 ms	17324 KB	Output is correct
19	Correct	451 ms	17324 KB	Output is correct
20	Correct	488 ms	26796 KB	Output is correct
21	Correct	522 ms	40884 KB	Output is correct
22	Correct	562 ms	54792 KB	Output is correct
23	Runtime error	1762 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.
24	Halted	0 ms	0 KB	-

답안 #56582

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.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
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0