Submission #393019

#	Time	Username	Problem	Language	Result	Execution time	Memory
393019		Mlxa	Shopping (JOI21_shopping)	C++14	10 / 100	419 ms	97320 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

namespace local {
	const int UP = 0, LEF = 2, RIG = 3;
	int n, l, r, choice = -1;
	vector<int> q;
	int cnt = 0;
}

void InitA(int nn, int ll, int rr) {
	using namespace local;
	n = nn;
	l = ll;
	r = rr;
}

void solve() {
	using namespace local;
	int v = 0, ql = 0, qr = 0;
	for (int i = 0; i < 20; ++i) {
		v += q[i] << i;
		ql += q[i + 20] << i;
		qr += q[i + 40] << i;
	}
	// cout << "? " << v << " " << ql << " " << qr << endl;
	if (!(ql <= l && r <= qr)) {
		cnt += 1;
		SendA(0);
		return;
	}
	if (r < v) {
		cnt += 2;
		SendA(1), SendA(0);
		return;
	}
	if (l > v) {
		cnt += 2;
		SendA(1), SendA(1);
		return;
	}
	choice = v;
}

void ex() {
	using namespace local;
	assert((int)q.size() == 20);
	int v = 0;
	for (int i = 0; i < 20; ++i) {
		v |= q[i] << i;
	}
	// cout << "EX " << v <<  " " << l << " " << r << endl;
	if (l <= v && v <= r) {
		choice = v;
		// cout << "SET " << v << endl;
	}
}

bool flag = false;

void ReceiveA(bool x) {
	using namespace local;
	q.push_back(x);
	// if (q.size() && q.size() % 20 == 0) {
		// cout << "LAST: ";
		// int v = 0;
		// for (int i = 0; i < 20; ++i) {
		// 	v |= q[q.size() - 20 + i] << i;
		// }
		// cout << v << endl;
	// }
	if (choice != -1) {
		return;
	}
	if (flag && (int)q.size() == 20) {
		ex();
		q.clear();
	}
	if ((int)q.size() == 60) {
		solve();
		q.clear();
		if (cnt + 2 > 18) {
			flag = true;
		}
	}
}

int Answer() {
	using namespace local;
	assert(choice != -1);
	return choice;
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

namespace my {

const int N = 1 << 20;
const int INF =   1e9;

bool bad[N];
pair<int, int> t[2 * N];
int query(int l, int r) {
	pair<int, int> res = make_pair(INF, -1);
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			res = min(res, t[l++]);
		}
		if (r % 2 == 0) {
			res = min(res, t[r--]);
		}
	}
	return res.y;
}
vector<pair<int, int>> g[N];
int lb[N], rb[N];
const int UP  = 0;
const int LEF = 2;
const int RIG = 3;

int pdfs(int l, int r) {
	int v = query(l, r);
	lb[v] = l, rb[v] = r;
	if (l < v) {
		int u = pdfs(l, v - 1);
		g[v].emplace_back(u, LEF);
		g[u].emplace_back(v, UP);
	}
	if (v < r) {
		int u = pdfs(v + 1, r);
		g[v].emplace_back(u, RIG);
		g[u].emplace_back(v, UP);
	}
	return v;
}
int sz[N];
void szdfs(int v, int p) {
	sz[v] = 1;
	for (auto e : g[v]) {
		int u = e.x;
		if (u == p || bad[u]) {
			continue;
		}
		szdfs(u, v);
		sz[v] += sz[u];
	}
}
int cdfs(int v, int p, int s) {
	for (auto e : g[v]) {
		int u = e.x;
		if (u == p || bad[u]) {
			continue;
		}
		if (2 * sz[u] > s) {
			return cdfs(u, v, s);
		}
	}
	return v;
}
int center(int v) {
	szdfs(v, v);
	return cdfs(v, v, sz[v]);
}
void send(int len, int msk) {
	// cout << "send " << msk << endl;
	for (int i = 0; i < len; ++i) {
		SendB((msk >> i) & 1);
	}
}
void ask(int v) {
	send(20, v);
	send(20, lb[v]);
	send(20, rb[v]);
}
int root;
int state = -1;
int Acnt;

vector<pair<int, int>> srt;
void edfs(int v, int p) {
	srt.emplace_back(t[N + v].x, v);
	for (auto e : g[v]) {
		int u = e.x;
		if (u == p || bad[u]) {
			continue;
		}
		edfs(u, v);
	}
}

void express() {
	// cout << "EXPRESS " << lb[root] << " " << rb[root] << endl;
	edfs(root, root);
	sort(srt.begin(), srt.end());
	for (auto e : srt) {
		send(20, e.y);
	}
}
}

void InitB(int n, vector<int> p) {
	using namespace my;
	for (int i = 0; i < n; ++i) {
		t[N + i] = make_pair(p[i], i);
	}
	for (int i = N - 1; i > 0; --i) {
		t[i] = min(t[i + i], t[i + i + 1]);
	}
	root = pdfs(0, n - 1);
	root = center(root);
	bad[root] = true;
	ask(root);
}

void ReceiveB(bool y) {
	// cout << "ReceiveB " << y << endl;
	using namespace my;
	++Acnt;
	if (state == -1) {
		state = y;
	} else if (state == 1) {
		state = 2 + y;
	} else {
		assert(false);
	}
	if (state == 0 || state == 2 || state == 3) {
		// cout << "\t\twas " << lb[root] << " " << rb[root] << " " << t[N + root].x << endl;
		for (auto e : g[root]) {
			if (e.y == state) {
				root = e.x;
				break;
			}
		}
		// cout << "\t\tgo " << state << ": " << lb[root] << " " << rb[root] << " " << t[N + root].x << endl;
		root = center(root);
		bad[root] = true;
		state = -1;
		if (Acnt + 2 > 18) {
			express();
			return;
		}
		ask(root);
	}
}

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