oj.uz

Submission #386302

# Submission time Handle Problem Language Result Execution time Memory
386302 2021-04-06T10:20:59 Z model_code Shopping (JOI21_shopping) C++17
100 / 100
 212 ms 12320 KB 
#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) {
	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;
}
#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) {
	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);
		}
	}
}

Compilation message

Anna.cpp: In function 'void InitA(int, int, int)':
Anna.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < S.size(); i++) SendA(S[i] - '0');
      |                 ~~^~~~~~~~~~
Anna.cpp: At global scope:
Anna.cpp:30:5: warning: 'int {anonymous}::reindexed(int)' defined but not used [-Wunused-function]
   30 | int reindexed(int x) {
      |     ^~~~~~~~~

Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i = 1; i < val.size(); i++) {
      |                  ~~^~~~~~~~~~~~
Bruno.cpp: At global scope:
Bruno.cpp:18:5: warning: 'int {anonymous}::reindexed(int)' defined but not used [-Wunused-function]
   18 | int reindexed(int x) {
      |     ^~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 388 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 392 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 1 ms 388 KB Output is correct
14 Correct 2 ms 388 KB Output is correct
15 Correct 2 ms 388 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 392 KB Output is correct
18 Correct 2 ms 388 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 388 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 392 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 1 ms 388 KB Output is correct
14 Correct 2 ms 388 KB Output is correct
15 Correct 2 ms 388 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 392 KB Output is correct
18 Correct 2 ms 388 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 4 ms 508 KB Output is correct
23 Correct 3 ms 640 KB Output is correct
24 Correct 3 ms 556 KB Output is correct
25 Correct 2 ms 576 KB Output is correct
26 Correct 4 ms 640 KB Output is correct
27 Correct 4 ms 512 KB Output is correct
28 Correct 3 ms 620 KB Output is correct
29 Correct 5 ms 640 KB Output is correct
30 Correct 3 ms 612 KB Output is correct
31 Correct 3 ms 544 KB Output is correct
32 Correct 4 ms 528 KB Output is correct
33 Correct 3 ms 512 KB Output is correct
34 Correct 3 ms 512 KB Output is correct
35 Correct 3 ms 512 KB Output is correct
36 Correct 2 ms 512 KB Output is correct
37 Correct 2 ms 516 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 12144 KB Output is correct
2 Correct 170 ms 12276 KB Output is correct
3 Correct 153 ms 12276 KB Output is correct
4 Correct 212 ms 12276 KB Output is correct
5 Correct 184 ms 12284 KB Output is correct
6 Correct 152 ms 12200 KB Output is correct
7 Correct 178 ms 12280 KB Output is correct
8 Correct 157 ms 12208 KB Output is correct
9 Correct 178 ms 12320 KB Output is correct
10 Correct 181 ms 12204 KB Output is correct
11 Correct 150 ms 12256 KB Output is correct
12 Correct 149 ms 12280 KB Output is correct
13 Correct 140 ms 12200 KB Output is correct
14 Correct 145 ms 12288 KB Output is correct
15 Correct 145 ms 12280 KB Output is correct
16 Correct 190 ms 12284 KB Output is correct
17 Correct 153 ms 12288 KB Output is correct
18 Correct 166 ms 12276 KB Output is correct
19 Correct 152 ms 12272 KB Output is correct
20 Correct 172 ms 12276 KB Output is correct
21 Correct 195 ms 12280 KB Output is correct
22 Correct 188 ms 12240 KB Output is correct
23 Correct 168 ms 12204 KB Output is correct
24 Correct 167 ms 12196 KB Output is correct
25 Correct 171 ms 12292 KB Output is correct
26 Correct 155 ms 12280 KB Output is correct
27 Correct 157 ms 12280 KB Output is correct
28 Correct 164 ms 12192 KB Output is correct
29 Correct 145 ms 12288 KB Output is correct
30 Correct 157 ms 12280 KB Output is correct