oj.uz

Submission #667229

# Submission time Handle Problem Language Result Execution time Memory
667229 2022-11-30T20:58:45 Z rainboy Shopping (JOI21_shopping) C++17
100 / 100
 132 ms 16228 KB 
/* 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);
}
/* 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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4456 KB Output is correct
2 Correct 4 ms 4368 KB Output is correct
3 Correct 5 ms 4368 KB Output is correct
4 Correct 4 ms 4368 KB Output is correct
5 Correct 4 ms 4368 KB Output is correct
6 Correct 3 ms 4368 KB Output is correct
7 Correct 5 ms 4368 KB Output is correct
8 Correct 5 ms 4368 KB Output is correct
9 Correct 4 ms 4368 KB Output is correct
10 Correct 4 ms 4460 KB Output is correct
11 Correct 4 ms 4368 KB Output is correct
12 Correct 4 ms 4368 KB Output is correct
13 Correct 5 ms 4368 KB Output is correct
14 Correct 3 ms 4368 KB Output is correct
15 Correct 5 ms 4368 KB Output is correct
16 Correct 4 ms 4448 KB Output is correct
17 Correct 5 ms 4368 KB Output is correct
18 Correct 5 ms 4368 KB Output is correct
19 Correct 4 ms 4456 KB Output is correct
20 Correct 3 ms 4368 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4456 KB Output is correct
2 Correct 4 ms 4368 KB Output is correct
3 Correct 5 ms 4368 KB Output is correct
4 Correct 4 ms 4368 KB Output is correct
5 Correct 4 ms 4368 KB Output is correct
6 Correct 3 ms 4368 KB Output is correct
7 Correct 5 ms 4368 KB Output is correct
8 Correct 5 ms 4368 KB Output is correct
9 Correct 4 ms 4368 KB Output is correct
10 Correct 4 ms 4460 KB Output is correct
11 Correct 4 ms 4368 KB Output is correct
12 Correct 4 ms 4368 KB Output is correct
13 Correct 5 ms 4368 KB Output is correct
14 Correct 3 ms 4368 KB Output is correct
15 Correct 5 ms 4368 KB Output is correct
16 Correct 4 ms 4448 KB Output is correct
17 Correct 5 ms 4368 KB Output is correct
18 Correct 5 ms 4368 KB Output is correct
19 Correct 4 ms 4456 KB Output is correct
20 Correct 3 ms 4368 KB Output is correct
21 Correct 6 ms 4692 KB Output is correct
22 Correct 6 ms 4496 KB Output is correct
23 Correct 6 ms 4500 KB Output is correct
24 Correct 7 ms 4496 KB Output is correct
25 Correct 5 ms 4368 KB Output is correct
26 Correct 6 ms 4628 KB Output is correct
27 Correct 5 ms 4580 KB Output is correct
28 Correct 6 ms 4588 KB Output is correct
29 Correct 5 ms 4484 KB Output is correct
30 Correct 6 ms 4508 KB Output is correct
31 Correct 5 ms 4596 KB Output is correct
32 Correct 5 ms 4500 KB Output is correct
33 Correct 5 ms 4492 KB Output is correct
34 Correct 5 ms 4508 KB Output is correct
35 Correct 5 ms 4420 KB Output is correct
36 Correct 5 ms 4512 KB Output is correct
37 Correct 4 ms 4468 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16144 KB Output is correct
2 Correct 132 ms 12324 KB Output is correct
3 Correct 89 ms 12260 KB Output is correct
4 Correct 97 ms 16216 KB Output is correct
5 Correct 89 ms 16228 KB Output is correct
6 Correct 90 ms 16156 KB Output is correct
7 Correct 126 ms 12208 KB Output is correct
8 Correct 93 ms 12136 KB Output is correct
9 Correct 96 ms 12196 KB Output is correct
10 Correct 85 ms 12264 KB Output is correct
11 Correct 112 ms 16164 KB Output is correct
12 Correct 86 ms 12196 KB Output is correct
13 Correct 85 ms 12268 KB Output is correct
14 Correct 84 ms 12264 KB Output is correct
15 Correct 88 ms 12184 KB Output is correct
16 Correct 91 ms 12264 KB Output is correct
17 Correct 94 ms 12184 KB Output is correct
18 Correct 132 ms 12264 KB Output is correct
19 Correct 93 ms 12120 KB Output is correct
20 Correct 85 ms 12172 KB Output is correct
21 Correct 89 ms 12264 KB Output is correct
22 Correct 86 ms 12164 KB Output is correct
23 Correct 105 ms 12272 KB Output is correct
24 Correct 90 ms 12180 KB Output is correct
25 Correct 92 ms 12368 KB Output is correct
26 Correct 110 ms 12180 KB Output is correct
27 Correct 90 ms 12116 KB Output is correct
28 Correct 87 ms 12208 KB Output is correct
29 Correct 85 ms 12192 KB Output is correct
30 Correct 85 ms 12188 KB Output is correct