Submission #386302

#	Time	Username	Problem	Language	Result	Execution time	Memory
386302		model_code	Shopping (JOI21_shopping)	C++17	100 / 100	212 ms	12320 KiB

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) {
	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) {
	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 (stderr)

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 / 1
• Subtask 2: 9 / 9
• Subtask 3: 90 / 90