oj.uz

답안 #56576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56576 2018-07-11T20:56:46 Z Xellos Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 1020 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, 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[0] : cost[0]);
		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[2*i];
			cost_nw[1][i] = cost[2*i+1];
		}
		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--;
				}
				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++;
				}
			}
		}
		solve(d+1, B, cost_nw[0], 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_nw[1], 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[2*i+1-x];
		cost_sum[i] = cost[2*i] + cost[2*i+1];
	}
	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_normal, 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_sum, 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, 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 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 4 ms 572 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 4 ms 572 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 477 ms 27272 KB Output is correct
12 Correct 498 ms 37920 KB Output is correct
13 Correct 820 ms 47792 KB Output is correct
14 Correct 1020 ms 58648 KB Output is correct
15 Runtime error 787 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.
16 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 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 4 ms 572 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 477 ms 27272 KB Output is correct
12 Correct 498 ms 37920 KB Output is correct
13 Correct 820 ms 47792 KB Output is correct
14 Correct 1020 ms 58648 KB Output is correct
15 Runtime error 787 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.
16 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 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 4 ms 572 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Runtime error 197 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 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 4 ms 572 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 477 ms 27272 KB Output is correct
12 Correct 498 ms 37920 KB Output is correct
13 Correct 820 ms 47792 KB Output is correct
14 Correct 1020 ms 58648 KB Output is correct
15 Runtime error 787 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.
16 Halted 0 ms 0 KB -