QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24075#3097. ShoppingQingyu100 ✓129ms16872kbC++205.1kb2022-03-26 01:22:382023-01-17 11:00:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-17 11:00:23]
  • 评测
  • 测评结果:100
  • 用时:129ms
  • 内存:16872kb
  • [2022-03-26 01:22:38]
  • 提交

Anna

#include "Anna.h"
#include <bits/stdc++.h>

namespace {
	
int entropy(int x){return x == 1 ? 0 : 32 - __builtin_clz(x - 1);}
int top_bit(int x) {return 31 - __builtin_clz(x);}
const int MAX_N = 1000000;
const int MAX_T = 10000;
int N, L, R;
bool memory[MAX_T];
int size, at, next;
int query_limit;
int depth;
int l, r;
int s, t;

std::string encode_node(int k) {
	std::string ret = "";
	int d = top_bit(k + 1);
	if(d == 0) ret += "000";
	else if(d == 1) ret += "001";
	else {
		int s = d + 2;
		for(int i = 3; i >= 0; i--) ret += (s >> i & 1 ? "1" : "0");
	}
	for(int i = d - 1; i >= 0; i--) ret += ((k + 1) >> i & 1 ? "1" : "0");
	return ret;
}
int reindexed(int x) {
	if(x < s - l) return l + x;
	return t + (x - s + l);
}

}

void InitA(int N, int L, int R) {
	::N = N, ::L = L, ::R = R;
	l = 0, r = N;
	int k = 0, d = 0;
	while(d < 13) {
		int m = (l + r) / 2;
		if(R < m) {
			r = m, k = 2 * k + 1, d++;
		} else if(m < L) {
			l = m + 1, k = 2 * k + 2, d++;
		} else {
			break;
		}
	}
	std::string S = encode_node(k);
	for(int i = 0; i < S.size(); i++) SendA(S[i] - '0');
	query_limit = 18 - S.size();
	depth = d;
	int m = (l + r) / 2;
	s = m, t = s;
	size = at = 0;
	if(depth < 13 && (s - l) + (r - t) >= 2) {
		next = entropy(s - l + 1);
	} else next = -1;
}

void ReceiveA(bool x) {
	fprintf(stderr, "ReceiveA %d\n", x);
	memory[size++] = x;
	while(next == size) {
		query_limit--;
		int c = entropy(s - l + 1);
		int p = 0;
		for(int i = 0; i < c; i++) {
			if(memory[at++]) p |= 1 << i;
		}
		p += l;
		int a = t - s, b = r - l;
		int m = (a + b - 1) / 2;
		int q = p + m + 1;
		if(p <= L && R < q) {
			SendA(1);
			l = p, r = q;
		} else {
			SendA(0);
			s = p, t = q;
		}
		if(query_limit > 0 && (s - l) + (r - t) >= 2) {
			next = size + entropy(s - l + 1);
		} else next = -1;
	}
}

int Answer() {
	int c = -1;
	if(s != t) {
		int d = entropy(t - s);
		c = 0;
		for(int i = 0; i < d; i++) if(memory[at++]) c |= 1 << i;
		c += s;
	}
	std::vector <int> id;
	for(int i = l; i < s; i++) id.push_back(i);
	if(s != t) id.push_back(c);
	for(int i = t; i < r; i++) id.push_back(i);
	std::stack <int> st;
	st.push(id[0]);
	int last = 1;
	int ret = -1;
	if(L <= id[0] && id[0] <= R) ret = id[0];
	while(at < size) {
		if(memory[at++]) {
			st.push(id[last++]);
		} else {
			int t = st.top(); st.pop();
			if(L <= id[last] && id[last] <= R && ret == t) ret = id[last];
		}
		if(ret == -1 && L <= id[last] && id[last] <= R) ret = id[last];
	}
	return ret;
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

namespace {
	
int entropy(int x){return x == 1 ? 0 : 32 - __builtin_clz(x - 1);}
const int MAX_N = 1000000;
const int MAX_S = 18;
int N;
std::vector <int> P;
int ord[MAX_N];
bool memory[MAX_S];
int size, at;
int depth, node;
int l, r;
int s, t;

int reindexed(int x) {
	if(x < s) return x - l;
	return (s - l) + (x - t);
}

}

void InitB(int N, std::vector<int> P) {
	::N = N, ::P = P;
	depth = node = -1;
	size = at = 0;
	l = r = -1;
}

void ReceiveB(bool y) {
	fprintf(stderr, "ReceiveB %d\n", y);
	memory[size++] = y;
	if(depth == -1) {
		int d = 0;
		for(int i = 0; i < size; i++) {
			d <<= 1;
			if(memory[i]) d++;
		}
		if(size == 3) {
			if(d == 0) depth = 0;
			else if(d == 1) depth = 1;
		} else if(size == 4) {
			depth = d - 2;
		}
	}
	if(depth == -1) return;
	if(node == -1) {
		at = (depth < 2 ? 3 : 4);
		if(size == at + depth) {
			node = 0;
			for(int i = 0; i < depth; i++) {
				node <<= 1;
				if(memory[at + i]) node++;
			}
			at = size;
		}
	}
	if(node == -1) return;
	if(l == -1) {
		l = 0, r = N;
		for(int i = depth - 1; i >= 0; i--) {
			int m = (l + r) / 2;
			if(node >> i & 1) l = m + 1;
			else r = m;
		}
		int sz = 0;
		int m = (l + r) / 2;
		int a = m - 1, b = m + 1;
		ord[sz++] = m;
		while(l <= a || b < r) {
			if(b == r || (l <= a && P[a] >= P[b])) {
				ord[sz++] = a--;
			} else {
				ord[sz++] = b++;
			}
		}
		s = m, t = s;
	}
	if(at < size) {
		int a = t - s - 1, b = r - l;
		int m = (a + b) / 2;
		if(memory[at++]) {
			if(ord[m] <= s) {
				l = ord[m], r = l + m + 1;
			} else {
				r = ord[m] + 1, l = r - m - 1;
			}
		} else {
			if(ord[m] <= s) {
				s = ord[m], t = ord[m] + m + 1;
			} else {
				t = ord[m] + 1, s = t - m - 1;
			}
		}
	}
	if(depth < 13 && size < 18 && (s - l) + (r - t) >= 2) {
		int a = t - s, b = r - l;
		int m = (a + b - 1) / 2;
		int c = entropy(s - l + 1);
		int p;
		if(ord[m] <= s) p = ord[m];
		else p = ord[m] - m;
		p -= l;
		for(int i = 0; i < c; i++) SendB(p >> i & 1);
	} else {
		int c = s;
		if(s != t) {
			for(int i = s; i < t; i++) if(P[i] < P[c]) c = i;
			int d = entropy(t - s);
			for(int i = 0; i < d; i++) SendB((c - s) >> i & 1);
		}
		std::vector <int> val;
		for(int i = l; i < s; i++) val.push_back(P[i]);
		if(s != t) val.push_back(P[c]);
		for(int i = t; i < r; i++) val.push_back(P[i]);
		
		std::stack <int> st;
		st.push(val[0]);
		for(int i = 1; i < val.size(); i++) {
			int a = val[i];
			while(!st.empty() && st.top() > a) {
				st.pop(); SendB(0);
			}
			st.push(a);
			SendB(1);
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 2ms
memory: 3612kb

input:

0
0
0
-1
-1

output:

-1
-1
-1

input:


output:

Accepted: 3 0

result:

ok 

Test #2:

score: 1
Accepted
time: 1ms
memory: 3788kb

input:

0
0
0
-1
1
-1
-1

output:

-1
1
-1
-1
-1

input:


output:

Accepted: 4 1

result:

ok 

Test #3:

score: 1
Accepted
time: 3ms
memory: 3708kb

input:

0
0
0
-1
0
-1
-1
-1

output:

-1
0
-1
1
1
-1
-1

input:


output:

Accepted: 4 3

result:

ok 

Test #4:

score: 1
Accepted
time: 2ms
memory: 3640kb

input:

0
0
0
-1
0
-1
1
-1
-1
-1

output:

-1
1
0
-1
0
-1
1
0
1
-1
-1

input:


output:

Accepted: 5 6

result:

ok 

Test #5:

score: 1
Accepted
time: 0ms
memory: 3692kb

input:

0
0
0
-1
1
-1
1
1
-1
-1

output:

-1
1
0
-1
1
-1
-1
-1

input:


output:

Accepted: 6 3

result:

ok 

Test #6:

score: 1
Accepted
time: 1ms
memory: 3664kb

input:

0
0
0
-1
0
-1
1
-1
1
-1
0
-1
0
-1
1
-1
0
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
1
1
1
1
0
1
0
-1
0
0
0
0
0
0
0
0
-1
1
0
1
0
0
0
1
0
-1
1
0
1
1
1
1
0
-1
0
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
1
1
0
-1
0
1
0
-1
1
0
-1
1
1
1
1
0
0
0
1
0
0
0
1
-1
-1

input:


output:

Accepted: 13 67

result:

ok 

Test #7:

score: 1
Accepted
time: 0ms
memory: 3740kb

input:

0
0
1
0
-1
1
-1
0
-1
0
-1
1
-1
1
-1
0
-1
1
-1
0
-1
0
-1
-1
-1

output:

-1
1
1
1
0
0
1
0
0
-1
0
1
0
1
1
1
1
0
-1
1
0
1
1
1
1
0
-1
0
1
1
1
1
0
-1
1
1
1
1
0
-1
0
0
0
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
0
0
0
0
0
1
1
0
0
1
-1
-1

input:


output:

Accepted: 13 58

result:

ok 

Test #8:

score: 1
Accepted
time: 4ms
memory: 3712kb

input:

0
0
0
-1
1
-1
0
-1
1
-1
0
-1
0
-1
0
-1
0
-1
1
-1
1
-1
0
-1
-1
-1

output:

-1
1
1
1
0
0
1
1
1
0
-1
1
1
1
1
1
0
1
1
-1
1
0
0
1
1
1
1
0
-1
0
0
1
1
1
1
0
-1
0
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
1
1
0
-1
0
1
0
-1
1
0
-1
1
1
1
1
1
0
1
0
0
0
1
-1
-1

input:


output:

Accepted: 13 66

result:

ok 

Test #9:

score: 1
Accepted
time: 3ms
memory: 3712kb

input:

0
1
0
0
1
1
-1
0
-1
0
1
0
1
1
0
1
-1
-1
-1

output:

-1
1
0
1
0
1
0
0
-1
0
0
0
0
0
-1
0
0
1
1
1
1
0
1
1
-1
-1

input:


output:

Accepted: 14 21

result:

ok 

Test #10:

score: 1
Accepted
time: 3ms
memory: 3632kb

input:

1
0
0
1
0
1
0
0
1
1
1
-1
1
1
1
-1
-1

output:

-1
1
1
-1
-1
-1

input:


output:

Accepted: 14 2

result:

ok 

Test #11:

score: 1
Accepted
time: 5ms
memory: 3800kb

input:

0
0
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
1
-1
0
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
1
0
0
0
1
1
0
-1
1
1
1
0
0
0
1
1
-1
1
0
1
1
1
1
1
0
-1
0
1
1
1
1
1
0
-1
1
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
0
1
1
0
0
0
0
1
0
0
0
1
-1
-1

input:


output:

Accepted: 13 68

result:

ok 

Test #12:

score: 1
Accepted
time: 2ms
memory: 3720kb

input:

0
0
1
1
-1
0
-1
0
-1
1
-1
0
-1
0
-1
1
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
1
0
0
1
1
1
1
1
-1
0
0
1
1
1
1
1
0
-1
0
1
1
1
1
1
0
-1
1
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
0
0
0
0
0
0
0
0
0
1
-1
-1

input:


output:

Accepted: 13 57

result:

ok 

Test #13:

score: 1
Accepted
time: 3ms
memory: 3660kb

input:

0
0
0
-1
0
-1
1
-1
0
0
1
1
1
1
0
0
-1
-1
-1

output:

-1
1
0
0
0
0
0
0
0
0
-1
0
-1
0
-1
0
1
0
0
1
1
0
1
0
1
0
1
-1
-1

input:


output:

Accepted: 13 23

result:

ok 

Test #14:

score: 1
Accepted
time: 1ms
memory: 3656kb

input:

0
1
0
0
0
0
-1
0
-1
1
-1
1
-1
0
-1
1
-1
0
-1
0
-1
1
-1
-1
-1

output:

-1
1
1
0
0
1
1
1
-1
0
1
1
1
1
1
0
-1
1
1
1
1
1
0
-1
0
0
0
0
1
-1
0
0
0
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
1
0
0
1
0
0
0
0
0
1
-1
-1

input:


output:

Accepted: 14 49

result:

ok 

Test #15:

score: 1
Accepted
time: 0ms
memory: 3784kb

input:

0
0
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
1
0
0
0
-1
-1
-1

output:

-1
0
1
1
1
0
0
1
1
1
-1
1
1
1
0
0
1
1
1
0
-1
0
1
0
1
0
1
1
0
-1
1
1
0
1
0
1
0
-1
0
0
1
1
0
0
-1
0
0
0
0
-1
0
1
1
0
1
0
1
1
1
1
1
-1
-1

input:


output:

Accepted: 13 54

result:

ok 

Test #16:

score: 1
Accepted
time: 4ms
memory: 3608kb

input:

0
0
1
0
-1
0
-1
1
-1
1
-1
0
-1
0
-1
0
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
1
0
0
1
1
1
1
1
-1
0
0
1
1
1
1
1
0
-1
0
1
1
1
1
1
0
-1
1
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
1
1
0
-1
0
1
0
-1
1
0
-1
0
0
0
1
1
1
0
0
0
0
1
-1
-1

input:


output:

Accepted: 13 57

result:

ok 

Test #17:

score: 1
Accepted
time: 4ms
memory: 3780kb

input:

0
1
0
0
0
0
-1
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
1
-1
0
-1
-1
-1

output:

-1
0
0
1
1
1
1
1
-1
1
0
1
1
1
1
0
-1
0
1
1
1
1
0
-1
1
1
1
1
0
-1
1
1
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
0
0
1
0
1
0
1
0
0
1
-1
-1

input:


output:

Accepted: 14 48

result:

ok 

Test #18:

score: 1
Accepted
time: 2ms
memory: 3712kb

input:

1
0
0
0
0
1
1
0
0
0
-1
1
-1
1
-1
1
-1
0
-1
-1
-1

output:

-1
0
0
1
-1
1
0
-1
1
0
-1
1
-1
1
-1
-1

input:


output:

Accepted: 14 9

result:

ok 

Test #19:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

1
0
0
1
1
0
0
1
0
0
0
-1
1
-1
1
-1
1
-1
-1

output:

-1
1
0
-1
1
0
-1
1
-1
-1
-1

input:


output:

Accepted: 14 5

result:

ok 

Test #20:

score: 1
Accepted
time: 0ms
memory: 3796kb

input:

1
0
1
0
0
0
0
1
1
0
1
1
-1
1
-1
1
-1
-1

output:

-1
0
-1
1
-1
-1
-1

input:


output:

Accepted: 14 2

result:

ok 

Subtask #2:

score: 9
Accepted

Test #21:

score: 9
Accepted
time: 5ms
memory: 3872kb

input:

0
0
0
-1
0
-1
0
1
0
1
0
0
1
0
1
1
0
1
-1
-1
-1

output:

-1
1
0
0
1
1
1
0
1
1
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
-1
1
0
1
0
0
1
0
0
1
0
1
0
1
0
1
-1
-1

input:


output:

Accepted: 16 37

result:

points 1.0

Test #22:

score: 9
Accepted
time: 4ms
memory: 3828kb

input:

0
0
1
0
-1
0
-1
1
-1
0
0
0
0
0
0
0
0
1
1
-1
-1
-1

output:

-1
0
0
0
1
1
0
0
0
0
0
0
0
-1
0
0
0
0
0
-1
0
0
0
0
0
-1
0
0
1
0
1
1
0
0
0
1
0
1
1
-1
-1

input:


output:

Accepted: 16 35

result:

points 1.0

Test #23:

score: 9
Accepted
time: 6ms
memory: 3824kb

input:

0
0
0
-1
0
-1
1
-1
0
-1
1
-1
0
1
1
0
1
1
0
1
0
-1
-1
-1

output:

-1
0
0
0
0
1
1
1
1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
-1
0
1
0
0
1
0
0
0
0
0
0
-1
0
0
0
0
0
-1
0
0
0
0
0
-1
1
0
0
1
0
1
1
0
0
0
0
1
1
1
-1
-1

input:


output:

Accepted: 16 59

result:

points 1.0

Test #24:

score: 9
Accepted
time: 4ms
memory: 3716kb

input:

0
0
1
1
-1
0
-1
1
-1
0
-1
0
0
1
1
0
1
1
1
0
-1
-1
-1

output:

-1
0
1
0
0
0
0
1
0
1
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
1
0
1
1
0
0
-1
0
0
0
0
0
0
0
0
-1
0
1
1
0
0
0
0
0
1
0
1
1
1
-1
-1

input:


output:

Accepted: 16 53

result:

points 1.0

Test #25:

score: 9
Accepted
time: 4ms
memory: 3744kb

input:

1
1
1
1
0
0
1
0
1
0
1
0
0
0
0
0
0
-1
-1

output:

-1
-1
-1

input:


output:

Accepted: 17 0

result:

points 1.0

Test #26:

score: 9
Accepted
time: 4ms
memory: 3784kb

input:

0
0
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
1
-1
0
-1
0
-1
0
-1
-1
-1

output:

-1
0
0
0
1
0
0
0
1
1
0
1
1
0
-1
0
0
1
0
0
0
1
1
1
0
0
1
-1
0
1
0
0
0
1
1
1
0
0
1
0
-1
1
0
0
0
1
1
1
0
0
1
0
-1
0
0
0
1
1
1
0
0
1
0
-1
0
0
1
1
1
0
0
1
0
-1
0
1
1
1
0
0
1
0
-1
1
1
1
0
0
1
0
-1
1
1
0
0
1
0
-1
1
0
0
1
0
-1
1
0
1
0
-1
0
1
0
-1
1
0
-1
1
0
1
1
1
1
1
0
1
0
1
1
0
0
0
1
-1
-1

input:


output:

Accepted: 16 118

result:

points 1.0

Test #27:

score: 9
Accepted
time: 3ms
memory: 3760kb

input:

0
0
1
1
-1
0
-1
1
-1
0
-1
1
-1
1
-1
1
-1
0
-1
0
-1
0
-1
1
-1
0
-1
0
-1
-1
-1

output:

-1
1
1
0
0
0
0
1
1
1
0
0
1
-1
1
0
0
0
0
1
1
1
0
0
1
0
-1
1
0
0
0
1
1
1
0
0
1
0
-1
0
0
0
1
1
1
0
0
1
0
-1
0
0
1
1
1
0
0
1
0
-1
0
1
1
1
0
0
1
0
-1
1
1
1
0
0
1
0
-1
1
1
0
0
1
0
-1
1
0
0
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
1
-1
-1

input:


output:

Accepted: 16 102

result:

points 1.0

Test #28:

score: 9
Accepted
time: 3ms
memory: 3780kb

input:

0
0
0
-1
0
-1
1
-1
0
0
1
0
1
0
1
1
0
1
1
1
-1
-1
-1

output:

-1
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
-1
0
-1
1
1
0
0
0
1
0
1
1
1
0
1
1
0
1
-1
-1

input:


output:

Accepted: 17 30

result:

points 1.0

Test #29:

score: 9
Accepted
time: 3ms
memory: 3872kb

input:

0
0
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
0
-1
1
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
-1
-1

output:

-1
1
1
0
1
0
1
1
1
0
0
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
1
0
1
0
0
0
0
1
0
-1
1
1
1
0
0
0
0
0
0
1
0
-1
0
0
0
1
0
1
1
1
0
0
-1
1
0
0
1
0
1
1
0
-1
0
1
1
1
0
0
1
-1
1
1
0
1
1
-1
1
1
0
0
1
-1
1
0
0
1
0
-1
0
0
1
0
-1
0
1
0
-1
1
0
-1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
-1
-1

input:


output:

Accepted: 16 112

result:

points 1.0

Test #30:

score: 9
Accepted
time: 0ms
memory: 3804kb

input:

0
1
1
0
0
1
0
0
-1
0
-1
0
-1
1
-1
1
-1
0
1
0
1
0
-1
-1
-1

output:

-1
0
1
0
1
0
1
0
1
0
-1
1
0
1
0
1
0
0
0
-1
0
0
1
0
0
-1
0
0
0
0
0
-1
0
0
0
0
0
-1
1
0
1
0
0
1
1
1
1
1
-1
-1

input:


output:

Accepted: 17 42

result:

points 1.0

Test #31:

score: 9
Accepted
time: 5ms
memory: 3764kb

input:

0
0
1
1
-1
0
1
0
1
0
1
1
0
1
0
1
1
1
-1
-1
-1

output:

-1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
0
0
0
0
1
1
1
0
0
1
1
-1
-1

input:


output:

Accepted: 17 25

result:

points 1.0

Test #32:

score: 9
Accepted
time: 5ms
memory: 3828kb

input:

0
0
1
0
-1
0
-1
1
-1
1
-1
0
1
0
0
0
0
1
1
1
0
-1
-1
-1

output:

-1
1
0
0
0
0
0
0
0
0
0
0
0
-1
0
-1
0
-1
0
-1
0
0
1
0
0
0
1
1
1
0
0
1
1
-1
-1

input:


output:

Accepted: 17 28

result:

points 1.0

Test #33:

score: 9
Accepted
time: 0ms
memory: 3752kb

input:

0
1
0
0
1
0
-1
0
-1
1
-1
1
-1
0
-1
1
-1
1
-1
1
-1
1
-1
0
1
0
-1
-1
-1

output:

-1
0
0
1
0
1
0
0
0
1
0
0
-1
0
1
0
0
1
1
1
0
0
-1
0
0
0
0
0
0
0
0
-1
1
0
1
0
0
0
0
0
-1
0
0
0
-1
0
0
0
-1
0
0
0
-1
0
0
0
-1
0
0
0
-1
0
0
1
0
0
0
0
1
1
0
1
1
-1
-1

input:


output:

Accepted: 17 63

result:

points 1.0

Test #34:

score: 9
Accepted
time: 5ms
memory: 3752kb

input:

0
1
1
0
0
1
0
0
-1
1
-1
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
0
-1
1
-1
-1
-1

output:

-1
0
1
1
0
0
1
0
1
0
-1
0
1
0
1
0
0
1
0
-1
0
1
1
0
0
1
0
-1
1
1
1
0
1
0
-1
1
0
1
0
-1
0
0
1
-1
1
-1
1
-1
1
-1
1
1
1
1
1
1
1
1
0
1
-1
-1

input:


output:

Accepted: 17 50

result:

points 1.0

Test #35:

score: 9
Accepted
time: 4ms
memory: 3748kb

input:

1
0
0
0
1
1
1
1
0
0
-1
0
-1
0
-1
1
1
1
0
0
-1
-1
-1

output:

-1
0
1
1
1
1
0
0
-1
0
1
0
0
0
-1
0
1
-1
0
1
0
1
0
1
1
1
-1
-1

input:


output:

Accepted: 17 22

result:

points 1.0

Test #36:

score: 9
Accepted
time: 0ms
memory: 3728kb

input:

1
0
1
0
1
1
0
1
0
1
1
0
-1
0
-1
1
-1
0
0
0
-1
-1
-1

output:

-1
1
0
1
0
0
-1
1
1
0
-1
0
0
-1
1
0
1
0
1
1
-1
-1

input:


output:

Accepted: 17 16

result:

points 1.0

Test #37:

score: 9
Accepted
time: 1ms
memory: 3700kb

input:

1
1
0
0
0
0
1
0
1
0
1
1
0
1
-1
0
-1
0
1
-1
-1
-1

output:

-1
0
1
0
-1
0
0
-1
0
0
1
0
1
-1
-1

input:


output:

Accepted: 17 10

result:

points 1.0

Subtask #3:

score: 90
Accepted

Test #38:

score: 90
Accepted
time: 118ms
memory: 14860kb

input:

0
0
0
-1
0
-1
1
-1
0
-1
1
-1
1
-1
1
-1
1
-1
1
-1
0
-1
1
-1
0
-1
1
-1
0
-1
0
-1
1
-1
-1
-1

output:

-1
0
0
1
0
1
0
1
0
0
0
1
0
0
1
1
1
1
0
1
-1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
0
1
1
1
0
-1
1
1
0
1
0
0
1
0
1
0
1
1
1
1
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
1
1
1
1
1
0
1
0
0
1
0
0
0
0
-1
0
1
1
0
0
0
1
0
0
0
1
1
1
1
0
-1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
-1
0
1
0
0
1
0
0
0
1
1
1
1
0
-1
1
0
0
1
0
0
0
1
1...

input:


output:

Accepted: 18 271

result:

points 1.0

Test #39:

score: 90
Accepted
time: 90ms
memory: 14900kb

input:

0
1
0
1
0
1
1
-1
0
-1
0
-1
1
-1
1
-1
0
-1
0
1
0
1
0
1
-1
-1
-1

output:

-1
0
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
-1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
1
1
0
0
0
1
1
1
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
-1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
1
1
0
0
0
1
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1...

input:


output:

Accepted: 18 216

result:

points 1.0

Test #40:

score: 90
Accepted
time: 92ms
memory: 14696kb

input:

1
1
1
1
0
0
0
1
1
1
0
1
1
0
0
0
1
-1
-1
-1

output:

-1
0
1
1
0
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
1
0
0
1
1
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
1
0
0
0
1
0
1
1
1
1
1
0
0
0
0...

input:


output:

Accepted: 17 233

result:

points 1.0

Test #41:

score: 90
Accepted
time: 96ms
memory: 15036kb

input:

0
0
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
-1
-1

output:

-1
0
0
0
1
1
1
0
0
1
1
1
1
0
0
0
1
0
1
1
-1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
0
1...

input:


output:

Accepted: 18 274

result:

points 1.0

Test #42:

score: 90
Accepted
time: 93ms
memory: 15232kb

input:

0
0
0
-1
0
-1
0
-1
1
-1
1
-1
1
-1
0
-1
1
-1
1
-1
0
-1
0
-1
1
-1
1
-1
1
-1
1
-1
0
-1
-1
-1

output:

-1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
-1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
0
1...

input:


output:

Accepted: 18 244

result:

points 1.0

Test #43:

score: 90
Accepted
time: 94ms
memory: 15212kb

input:

0
0
0
-1
0
-1
1
-1
1
-1
0
1
1
1
1
0
1
1
0
1
0
0
-1
-1
-1

output:

-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
-1
0
-1
0
-1
0
1
1
0
1
1
0
0
0
1
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
-1
-1

input:


output:

Accepted: 18 102

result:

points 1.0

Test #44:

score: 90
Accepted
time: 114ms
memory: 14792kb

input:

0
1
0
1
1
0
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
0
-1
0
-1
1
-1
0
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
0
0
0
0
0
1
1
1
0
1
1
0
0
1
-1
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
1
1
0
1
0
1
0
0
0
0
1
-1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
0
1
1
0
1
1
0
1
-1
0
0
0
1
1
0
1
1
0
1
-1
0
0
0
1
1
0
1
1
0
1
-1
0
0
0
1
0
1
1
1
1
0
-1
0
0
0
0
1
1
1
1
-1
0
1
0
1
1
1
1
0
-1
1
0
1
1
1
1
0
-1
0
0
1
0
1
0
1
1
0
...

input:


output:

Accepted: 18 258

result:

points 1.0

Test #45:

score: 90
Accepted
time: 99ms
memory: 14792kb

input:

0
1
1
0
0
1
1
0
-1
0
-1
1
-1
1
-1
1
-1
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
-1
-1

output:

-1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
1
0
1
0
-1
1
1
1
0
1
1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
-1
1
1
0
0
0
0
1
0
0
-1
0
0
0
0
0
0
0
-1
0
1
1
0
0
0
0
-1
0
1
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
1...

input:


output:

Accepted: 18 240

result:

points 1.0

Test #46:

score: 90
Accepted
time: 84ms
memory: 14820kb

input:

1
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
1
-1
-1
-1

output:

-1
1
1
0
0
0
1
1
0
1
1
1
0
1
1
1
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
1
1
0
0
0
1
1
1
0
1
0
1
1
0
1
0
1
0
0
0
1
1
1
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
1
0
0
0
0
1
1
0
0
1...

input:


output:

Accepted: 17 236

result:

points 1.0

Test #47:

score: 90
Accepted
time: 88ms
memory: 14812kb

input:

1
0
0
1
1
0
0
0
1
1
0
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
1
1
0
1
0
0
1
1
1
0
-1
0
0
1
0
1
1
1
0
0
0
1
0
-1
0
0
0
1
1
1
1
1
0
0
-1
0
1
0
1
1
1
1
1
0
0
-1
1
0
0
0
1
0
1
1
0
-1
0
1
0
1
1
1
1
0
-1
1
0
1
1
1
1
0
-1
0
1
1
1
1
0
0
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
1
0
1
0
1
1
0
0
1
1
0
1
1
1
0
1
0
0
1
1
1
0
0
1
1
0
1
0
0
...

input:


output:

Accepted: 18 185

result:

points 1.0

Test #48:

score: 90
Accepted
time: 82ms
memory: 15100kb

input:

0
0
0
-1
0
-1
0
-1
1
-1
1
-1
0
-1
0
-1
1
-1
0
-1
1
-1
1
-1
1
-1
0
-1
0
-1
0
-1
0
-1
-1
-1

output:

-1
0
0
0
0
0
0
1
1
1
0
1
1
1
1
0
1
1
1
0
-1
0
1
0
1
1
1
0
0
1
0
0
0
0
1
1
0
1
0
-1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
0
1
0
1
1
0
1
0
1
1
0
0
0
1
0
1
0
-1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
0
1
0
1...

input:


output:

Accepted: 18 272

result:

points 1.0

Test #49:

score: 90
Accepted
time: 89ms
memory: 14668kb

input:

1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
1
-1
1
-1
0
-1
-1
-1

output:

-1
1
0
1
0
1
0
1
-1
0
0
1
0
0
1
-1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
1
-1
-1

input:


output:

Accepted: 18 137

result:

points 1.0

Test #50:

score: 90
Accepted
time: 91ms
memory: 16872kb

input:

1
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
-1
1
-1
0
-1
-1
-1

output:

-1
1
1
0
1
1
0
1
-1
1
0
0
0
1
-1
0
0
1
1
1
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
-1
-1

input:


output:

Accepted: 18 139

result:

points 1.0

Test #51:

score: 90
Accepted
time: 87ms
memory: 14708kb

input:

0
1
0
0
1
0
-1
0
0
0
1
0
1
0
1
1
1
1
0
-1
-1
-1

output:

-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
0
0
1
1
0
1
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
...

input:


output:

Accepted: 18 155

result:

points 1.0

Test #52:

score: 90
Accepted
time: 93ms
memory: 14904kb

input:

0
1
0
0
1
0
-1
0
1
0
1
0
0
1
0
0
1
0
0
-1
-1
-1

output:

-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
1
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
1
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
...

input:


output:

Accepted: 18 156

result:

points 1.0

Test #53:

score: 90
Accepted
time: 80ms
memory: 14896kb

input:

0
0
1
0
-1
0
-1
1
-1
0
-1
0
-1
0
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
0
-1
1
-1
-1
-1

output:

-1
0
1
0
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
-1
0
1
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
1
1
1
0
0
1
0
1
1
1
1
0
-1
0
1
1
0
0
1
0
1
0
0
1
1
1
1
0
-1
1
0
1
0
1
0
1
0
0
1
1
1
1
0
-1
0
0
0
0
1
0
0
0
1
1
1
1
0
-1
0
0
0
0
1
0
0
1
1
1
1
0
-1
1
0
0
1
1
0
1
1
1
1
0
-1
0
1
1
1
0
1
1
1
1
0
-1
0
0
0
0
1
1
1
1
0
...

input:


output:

Accepted: 18 243

result:

points 1.0

Test #54:

score: 90
Accepted
time: 99ms
memory: 14704kb

input:

0
1
0
0
0
1
-1
0
-1
1
-1
1
-1
0
-1
0
-1
0
-1
1
-1
0
-1
1
-1
0
-1
1
-1
1
-1
-1
-1

output:

-1
0
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
-1
0
0
0
0
1
0
1
1
0
0
0
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
-1
0
1
0
1
1
1
0
0
0
0
1
0
1
0
-1
0
0
0
1
1
1
1
1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
1
0
0
1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
-1
1
1
0
0
1
1
0
0
0
-1
0
0
0
0...

input:


output:

Accepted: 18 281

result:

points 1.0

Test #55:

score: 90
Accepted
time: 107ms
memory: 14716kb

input:

0
1
0
1
0
1
1
-1
0
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
0
-1
1
-1
0
-1
0
-1
-1
-1

output:

-1
1
0
0
0
1
1
0
1
1
0
0
0
0
0
0
1
-1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
0
0
-1
0
1
0
0
0
1
0
1
0
1
1
1
1
0
0
-1
0
1
0
0
0
1
1
0
1
1
1
1
0
0
-1
1
1
1
0
1
0
1
1
1
0
0
1
0
-1
1
0
0
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
1
0
1
1
1
1
0
-1
1
0
1
0
0
1
0
0
1
-1
0
0
1
0
1
1
1
1
0
-1
1
0
0
0
1
1
-1
1
0
0
0
1
1
-1
1
1
1
1
1
...

input:


output:

Accepted: 18 261

result:

points 1.0

Test #56:

score: 90
Accepted
time: 122ms
memory: 14740kb

input:

0
1
1
0
1
0
1
0
-1
0
-1
1
-1
1
-1
0
-1
0
-1
0
-1
0
-1
1
-1
0
-1
0
-1
-1
-1

output:

-1
0
1
0
1
0
0
1
1
0
0
1
1
1
1
0
-1
1
1
1
0
1
0
1
0
0
1
1
1
1
0
-1
1
0
1
1
0
1
1
1
0
1
1
1
0
-1
1
1
0
0
1
0
1
1
1
1
1
0
-1
0
1
1
1
1
0
1
1
1
1
0
-1
0
0
0
0
1
1
1
1
1
0
-1
1
1
0
1
0
0
0
0
1
-1
0
0
0
0
1
0
0
1
0
-1
1
1
0
0
0
0
1
-1
1
1
0
1
1
0
0
-1
1
0
1
0
0
1
1
0
1
1
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1...

input:


output:

Accepted: 18 245

result:

points 1.0

Test #57:

score: 90
Accepted
time: 89ms
memory: 14872kb

input:

0
1
1
1
0
1
1
0
1
-1
1
-1
0
-1
0
-1
1
-1
1
-1
0
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
1
0
1
0
1
0
1
1
1
1
1
0
-1
1
1
1
0
0
0
0
1
0
1
1
1
0
-1
0
0
1
0
0
1
0
0
1
0
1
1
-1
1
0
0
0
0
1
0
1
1
1
1
0
-1
0
0
0
0
1
0
1
1
1
1
0
-1
1
1
0
0
1
1
0
1
1
-1
0
0
1
0
1
1
1
1
0
-1
0
1
0
1
1
1
1
0
-1
1
0
1
1
1
1
0
-1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
...

input:


output:

Accepted: 18 227

result:

points 1.0

Test #58:

score: 90
Accepted
time: 75ms
memory: 14884kb

input:

1
0
0
0
0
0
0
1
0
1
-1
0
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
0
-1
-1
-1

output:

-1
0
1
1
1
1
0
1
0
1
0
0
1
0
-1
1
0
0
0
1
0
0
1
1
1
1
0
-1
0
1
1
1
0
1
1
0
1
-1
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
-1
1
0
0
0
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0...

input:


output:

Accepted: 18 203

result:

points 1.0

Test #59:

score: 90
Accepted
time: 85ms
memory: 14684kb

input:

1
0
0
1
0
0
1
0
0
1
0
-1
0
-1
0
-1
0
-1
1
-1
1
-1
0
-1
0
-1
-1
-1

output:

-1
0
1
0
0
1
0
0
1
1
1
1
0
-1
0
1
0
0
1
0
1
1
1
1
0
-1
1
1
0
1
0
1
1
1
1
0
-1
1
0
0
1
1
1
1
1
0
-1
0
1
1
0
1
1
1
0
-1
0
1
0
0
0
0
1
-1
0
0
0
0
0
1
0
-1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
1
0
0
1
0
1
0
0
...

input:


output:

Accepted: 18 199

result:

points 1.0

Test #60:

score: 90
Accepted
time: 100ms
memory: 14784kb

input:

1
0
1
0
1
1
0
0
1
0
1
1
-1
0
-1
1
-1
0
-1
0
-1
1
-1
1
-1
-1
-1

output:

-1
1
1
1
1
0
0
1
1
1
1
0
-1
0
1
0
1
0
1
1
1
1
0
-1
1
1
1
1
0
1
1
1
0
-1
1
0
1
0
1
1
1
0
-1
0
1
0
1
1
1
0
-1
0
1
1
0
0
1
-1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
1...

input:


output:

Accepted: 18 184

result:

points 1.0

Test #61:

score: 90
Accepted
time: 108ms
memory: 14812kb

input:

1
0
1
1
1
0
1
0
1
1
1
0
1
-1
0
-1
1
-1
1
-1
1
-1
1
-1
-1
-1

output:

-1
0
0
0
1
0
1
1
1
1
0
-1
1
1
0
1
1
1
1
1
0
-1
0
0
1
1
0
1
1
0
-1
0
1
0
1
1
1
0
0
-1
1
0
0
0
0
1
0
-1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
...

input:


output:

Accepted: 18 170

result:

points 1.0

Test #62:

score: 90
Accepted
time: 103ms
memory: 14780kb

input:

1
1
0
0
1
1
1
1
0
1
1
1
1
0
-1
0
-1
1
-1
1
-1
0
-1
-1
-1

output:

-1
0
0
0
1
1
0
0
1
0
-1
0
0
0
1
0
0
1
0
-1
0
0
0
0
0
0
0
-1
1
1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
0
0
1
0
1
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
1
1
0
1
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0...

input:


output:

Accepted: 18 162

result:

points 1.0

Test #63:

score: 90
Accepted
time: 84ms
memory: 14860kb

input:

1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
-1
0
-1
1
-1
0
-1
-1
-1

output:

-1
1
0
0
1
1
1
1
0
-1
0
1
1
1
1
1
0
-1
0
1
0
0
0
1
-1
0
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
1
1
0
0
1
1
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
0
0
0
0
...

input:


output:

Accepted: 18 151

result:

points 1.0

Test #64:

score: 90
Accepted
time: 84ms
memory: 14876kb

input:

1
1
1
0
0
1
0
1
0
0
1
0
1
1
0
0
-1
0
-1
1
-1
-1
-1

output:

-1
1
0
1
0
1
1
0
-1
0
0
1
1
1
0
-1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
1
0
1
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
0
1
-1
-1

input:


output:

Accepted: 18 141

result:

points 1.0

Test #65:

score: 90
Accepted
time: 93ms
memory: 14712kb

input:

1
1
1
1
0
1
0
1
0
1
0
0
0
0
1
0
0
-1
-1
-1

output:

-1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-1
-1

input:


output:

Accepted: 17 120

result:

points 1.0

Test #66:

score: 90
Accepted
time: 74ms
memory: 14740kb

input:

1
1
1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
-1
-1
-1

output:

-1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0...

input:


output:

Accepted: 17 240

result:

points 1.0

Test #67:

score: 90
Accepted
time: 129ms
memory: 14884kb

input:

1
1
1
0
1
0
0
0
0
1
0
0
0
0
0
0
-1
1
-1
0
-1
-1
-1

output:

-1
0
1
0
0
0
0
1
-1
1
0
1
0
0
1
-1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
0
0
0
0
1
1
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
1
0
0
1
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
1
-1
-1

input:


output:

Accepted: 18 138

result:

points 1.0

Extra Test:

score: 0
Extra Test Passed