Submission #396386

#	Time	Username	Problem	Language	Result	Execution time	Memory
396386		ChrisT	Shopping (JOI21_shopping)	C++17	10 / 100	102 ms	596 KiB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
const int MN = 1e6 + 5;
vector<int> go,mx; int ind = 0, bit = 0, L, R;
void InitA (int n, int l, int r) {
	L = l; R = r;
	int baseL = 0, baseR = 0;
	for (int i = 14; i > 5; i--) {
		SendA(l>>i&1);
		baseL |= (l & (1 << i));
	}
	for (int i = 14; i > 5; i--) {
		SendA(r>>i&1);
		baseR |= (r & (1 << i));
	}
	for (int low = 0; low < (1 << 6); low++) {
		go.push_back(baseL | low);
		go.push_back(baseR | low);
	}
	sort(go.begin(),go.end());
	go.erase(unique(go.begin(),go.end()),go.end());
	mx.resize((int)go.size()*5);
}
void ReceiveA (bool x) {
	mx[ind] |= (((int)x) << bit);
	if ((++bit) > 14) {
		bit = 0; ++ind;
	}
}
int Answer () {
	int st = -1, ret = 1e9, id = -1;
	for (int i = 0; i < (int)go.size(); i++) {
		if (go[i] == L) st = i;
	}
	for (int i = st; i < (int)go.size(); i++) {
		if (mx[4 * i] < ret) {
			ret = mx[4 * i];
			id = mx[4 * i + 1];
		}
		if (go[i] == R) break;
		if (mx[4 * i + 2] < ret) {
			ret = mx[4 * i + 2];
			id = mx[4 * i + 3];
		}
	}
	return id;
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
const int MN = 1e6 + 5;
vector<int> go,mx,p,has(2); int ind = 0, bit = 14, N;
void InitB (int n, vector<int> pp) {
	p=pp;
}
void relay (int x) {
	for (int j = 0; j <= 14; j++) SendB(x >> j & 1);
}
void ReceiveB (bool x) {
	has[ind] |= (((int)x) << bit);
	if ((--bit) < 6) {
		bit = 14; ++ind;
	}
	if (ind > 1) {
		for (int low = 0; low < (1 << 6); low++) {
			go.push_back(has[0] | low);
			go.push_back(has[1] | low);
		}
		sort(go.begin(),go.end());
		go.erase(unique(go.begin(),go.end()),go.end());
		for (int i = 0; i < (int)go.size(); i++) {
			relay(p[go[i]]); relay(go[i]);
			if (i + 1 < (int)go.size()) {
				int mx = 1e4 + 1, id = 0;
				for (int j = go[i] + 1; j < go[i+1]; j++) {
					if (p[j] < mx) {
						mx = p[j];
						id = j;
					}
				}
				relay(mx); relay(id);
			}
		}
	}
}

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