Submission #667229

#	Time	Username	Problem	Language	Result	Execution time	Memory
667229		rainboy	Shopping (JOI21_shopping)	C++17	100 / 100	132 ms	16228 KiB

Anna

/* https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/shopping-review.pdf */
#include "Anna.h"
#include <cassert>
#include <vector>

using namespace std;

namespace A {
	const int N = 1000000, A = 18, B = 300, D = 14, INF = 0x3f3f3f3f;
	int ql, qr, a, k, l, x, l1, r1, l2, r2, i_, zz[(N + 1) * 2], dd[N + 1], n, m;
	int lg(int n) {
		int l = 0;
		while (1 << l < n)
			l++;
		return l;
	}
	void check() {
		int good = 1;
		for (int d = 0; d <= D; d++) {
			int a = A - (d == 0 ? 3 : 4) - d, b = 0, n = N;
			for (int h = 0; h < d; h++)
				n /= 2;
			for (int h = 0; h < a; h++) {
				n = (n + 1) / 2;
				b += lg(n / 2 + 1);
			}
			b += lg(N + 1) + (n + 1) * 2;
			if (b > B)
				good = 0;
		}
		assert(good);
	}
	int idx(int i) {
		if (i < l1)
			return i - l2;
		else if (i <= r1)
			return l1 - l2;
		else
			return l1 - l2 + i - r1;
	}
	void get_tree(int l, int r, int d) {
		if (l < r) {
			int i, c;
			for (i = l + 1, c = 1; i < r && c > 0; i++)
				c += zz[i] == 0 ? 1 : -1;
			get_tree(l + 1, i - 1, d + 1);
			dd[n++] = d;
			get_tree(i, r, d + 1);
		}
	}
}

void InitA(int n, int ql_, int qr_) {
	A::check();
	A::ql = ql_, A::qr = qr_, A::a = A::A;
	int d = 0, l = 0, r = A::N - 1, x = 0;
	while (1) {
		int m = (l + r) / 2;
		if (d >= A::D || A::ql <= m && m <= A::qr) {
			A::l1 = m + 1, A::r1 = m, A::l2 = l, A::r2 = r;
			break;
		}
		if (A::qr < m)
			r = m - 1, x = x << 1 | 0;
		else
			l = m + 1, x = x << 1 | 1;
		d++;
	}
	d += A::D + 1;
	for (int h = A::lg(d + 1) - 2; h >= 0; h--)
		SendA(d >> h & 1), A::a--;
	d -= A::D + 1;
	for (int h = d - 1; h >= 0; h--)
		SendA(x >> h & 1), A::a--;
	if (A::a > 0)
		A::k = (A::l1 - A::l2 + A::r2 - A::r1) / 2, A::l = A::lg(A::k + 1), A::x = 0, A::i_ = 0;
	else
		A::l = A::lg(A::N + 1);
}

void ReceiveA(bool z) {
	if (A::a > 0) {
		A::x = A::x << 1 | z;
		if (--A::l == 0) {
			int l_ = A::l1 - A::x, r_ = A::r1 + A::k - A::x, z = l_ <= A::ql && A::qr <= r_ ? 0 : 1;
			SendA(z), A::a--;
			if (z == 0)
				A::l2 = l_, A::r2 = r_;
			else
				A::l1 = l_, A::r1 = r_;
			if (A::a > 0)
				A::k = (A::l1 - A::l2 + A::r2 - A::r1) / 2, A::l = A::lg(A::k + 1), A::x = 0;
			else
				A::l = A::lg(A::N + 1);
		}
	} else if (A::l > 0)
		A::i_ = A::i_ << 1 | z, A::l--;
	else
		A::zz[A::m++] = z;
}

int Answer() {
	int l = A::idx(A::ql), r = A::idx(A::qr);
	A::get_tree(0, A::m, 0);
	int i1 = -1;
	for (int i = l; i <= r; i++)
		if (i1 == -1 || A::dd[i1] > A::dd[i])
			i1 = i;
	return i1 == A::l1 - A::l2 ? A::i_ : (i1 < A::l1 - A::l2 ? i1 + A::l2 : i1 + A::l2 + A::r1 - A::l1);
}

Bruno

/* https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/shopping-review.pdf */
#include "Bruno.h"
#include <vector>

using namespace std;

namespace B {
	const int N = 1000000, A = 18, B = 300, D = 14, INF = 0x3f3f3f3f;
	int aa[N], aa_[N + 1], ll[N + 1], rr[N + 1], mode, d, l, r, a, lower, upper, mid;
	int lg(int n) {
		int l = 0;
		while (1 << l < n)
			l++;
		return l;
	}
	void send_tree(int *aa, int n) {
		if (n > 0) {
			int i_ = -1;
			for (int i = 0; i < n; i++)
				if (i_ == -1 || aa[i_] > aa[i])
					i_ = i;
			SendB(0);
			if (i_ > 0)
				send_tree(aa, i_);
			SendB(1);
			if (i_ + 1 < n)
				send_tree(aa + i_ + 1, n - 1 - i_);
		}
	}
	void send() {
		if (a > 0) {
			mid = (lower + upper) / 2;
			int x = ll[lower] - ll[mid], l = lg(mid - lower + 1);
			for (int h = l - 1; h >= 0; h--)
				SendB(x >> h & 1);
		} else {
			int i_ = N;
			for (int i = ll[lower]; i <= rr[lower]; i++)
				if (i_ == N || aa[i_] > aa[i])
					i_ = i;
			int l = lg(N + 1);
			for (int h = l - 1; h >= 0; h--)
				SendB(i_ >> h & 1);
			int n = 0;
			for (int i = ll[upper]; i < ll[lower]; i++)
				aa_[n++] = aa[i];
			aa_[n++] = i_ == N ? N : aa[i_];
			for (int i = rr[lower] + 1; i <= rr[upper]; i++)
				aa_[n++] = aa[i];
			send_tree(aa_, n);
		}
	}
	void init() {
		int m = (l + r) / 2;
		ll[0] = m + 1, rr[0] = m, ll[1] = m, rr[1] = m;
		for (int k = 2; k <= r - l + 1; k++) {
			ll[k] = ll[k - 1], rr[k] = rr[k - 1];
			if (rr[k] == r || ll[k] > l && aa[ll[k] - 1] > aa[rr[k] + 1])
				ll[k]--;
			else
				rr[k]++;
		}
		lower = 0, upper = r - l + 1, send();
	}
}

typedef vector<int> vi;

void InitB(int n, vi pp) {
	B::mode = 0;
	for (int i = 0; i < n; i++)
		B::aa[i] = pp[i];
	for (int i = n; i < B::N; i++)
		B::aa[i] = i + 1;
	B::d = 1, B::l = 0, B::r = B::N - 1, B::a = B::A;
}

void ReceiveB(bool z) {
	B::a--;
	if (B::mode == 0) {
		B::d = B::d << 1 | z;
		if (B::d > B::D) {
			B::d -= B::D + 1, B::mode = 1;
			if (B::d == 0)
				B::init(), B::mode = 2;
		}
	} else if (B::mode == 1) {
		int m = (B::l + B::r) / 2;
		if (z == 0)
			B::r = m - 1;
		else
			B::l = m + 1;
		if (--B::d == 0)
			B::init(), B::mode = 2;
	} else {
		if (z == 0)
			B::upper = B::mid;
		else
			B::lower = B::mid;
		B::send();
	}
}

Compilation message (stderr)

Anna.cpp: In function 'void InitA(int, int, int)':
Anna.cpp:59:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |   if (d >= A::D || A::ql <= m && m <= A::qr) {
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~

Bruno.cpp: In function 'void B::init()':
Bruno.cpp:58:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |    if (rr[k] == r || ll[k] > l && aa[ll[k] - 1] > aa[rr[k] + 1])
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 9 / 9
• Subtask 3: 90 / 90