Submission #1222652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222652		sleepntsheep	Shopping (JOI21_shopping)	C++20	10 / 100	64 ms	12732 KiB

Anna

#include "Anna.h"
#include <vector>

namespace {
	const int B = 20
		,		N = 10000;

	int n, l, r, bel[N], ans, count, pre[N], suf[N]
		, lb, rb, num, at, arg, min, num2;
}

void InitA(int n, int l, int r) {
	::n = n;
	::l = l;
	::r = r;
	for (int i = 0; i < n; ++i)
		bel[i] = i / B;

	lb = bel[l] + 1 , rb = bel[r];

	for (int i = 8; i >= 0; --i)
		SendA((lb >> i) & 1);
	for (int i = 8; i >= 0; --i)
		SendA((rb >> i) & 1);

	count = 0;
	ans = 0;
	num = 0;
	num2 = 0;
	at = lb * B + B - 1;
}

void ReceiveA(bool x) {
	if (count < 20) {
		arg ^= (x ? 1 : 0) << (count);
	} else if (count < 40) {
		min ^= (x ? 1 : 0) << (count - 20);
		if (count == 39)
			if (bel[l] + 1 >= bel[r])
				min = 1e9;
	} else {
		int y = (count - 40) % 40;
		if (y < 20) {
			num |= (x ? 1 : 0) << y;
		} else {
			y -= 20;
			num2 |= (x ? 1 : 0) << y;
			if (y == 19) {
				if (at == lb * B) {
					at = rb * B;
				} else if (at <= lb * B + B - 1) {
					--at;
				} else {
					++at;
				}
				if (num >= l && num <= r && num2 < min)
					min = num2, arg = num;
				num = num2 = 0;
			}
		}
	}
	++count;
}

int Answer() {
	return arg;
}

Bruno

#include "Bruno.h"
#include <cstdio>
#include <vector>

namespace {
	const int B = 20, N = 10000;

	std::vector<int> P;
	int n, bel[N], low[N]
		, tot, count;

	int ij(int i, int j) {
		return P[i] < P[j]? i: j;
	}
}

void SendInt(int x, int bits) {
	for (int b = 0; b < bits; ++b)
		SendB((x >> b) & 1);
}

void InitB(int n, std::vector<int> P) {
	::P = P;
	::n = n;
	for (int i = 0; i < n; ++i)
		bel[i] = i / B, low[i / B] = i;
	for (int i = 0; i < n; ++i)
		low[i / B] = ij(low[i / B], i);
	count = 0;
}

void ReceiveB(bool y) {
	tot |= (y? 1 : 0) << (18 - count - 1);
	++count;

	if (count == 18) {
		int lb = tot >> 9, rb = tot & 511;

		int x = lb * B >= n ? n - 1 : lb * B;
		for (int i = lb; i < rb; ++i)
			x = ij(x, low[i]);
		SendInt(x, 20);
		SendInt(P[x], 20);

		int at, run;
		at = lb * B - 1 >= n ? n - 1 : lb * B - 1;
		run = at;
		for (; at >= lb * B - B && at >= 0; --at) {
			SendInt(at, 20);
			SendInt(P[at], 20);
			run = ij(run, at);
		}
		at = rb * B;
		run = at;
		for (; at < rb * B + B && at < n; ++at) {
			SendInt(at, 20);
			SendInt(P[at], 20);
			run = ij(run, at);
		}
	}
}

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