Submission #1209512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209512		PenguinsAreCute	Shopping (JOI21_shopping)	C++17	1 / 100	117 ms	12420 KiB

Anna

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

namespace {
	const int K = 1384;
	vector<bool> rec;
	int L, R;
	int getMin(vector<bool> val, int l, int r) {
		int N = int(val.size()) / 2, cnt = 0;
		vector<int> st;
		for(auto i: val) {
			if(i) {
				st.push_back(cnt);
				if((cnt++) == r)
					return *lower_bound(st.begin(),st.end(),l);
			} else
				st.pop_back();
		}
		assert(0);
	}
	vector<int> toTer(vector<bool> b) {
		vector<int> bin;
		for(auto i: b)
			bin.push_back(i);
		vector<int> ans(2*K);
		for(int i=0;i<2*K;i++)
			for(int j=4388;j--;) {
				(j?bin[j-1]:ans[i]) += 2 * (bin[j] % 3);
				bin[j] /= 3;
			}
		for(int i=0;i<2*K;i++)
			ans[i] /= 3;
		return ans;
	}
	pair<vector<bool>,vector<bool>> dec(vector<int> t) {
		vector<bool> a, b;
		for(auto i: t) {
			a.push_back(i);
			if(i)
				b.push_back(i-1);
		}
		return {a,b};
	}
}

void InitA(int N, int L, int R) {
	::L = L;
	::R = R;
	int A = L / K, B = R / K;
	int X = B * (B + 1) / 2 + A;
	for(int i=0;i<18;i++)
		SendA(X & (1 << i));
}

void ReceiveA(bool x) {
	rec.push_back(x);
}

int Answer() {
	if((L / K) == (R / K))
		return (L / K) * K + getMin(rec, L % K, R % K);
	// pls end my depression and suffering.
	auto [pref, ord] = dec(toTer(vector<bool>(rec.begin(),rec.begin()+4388)));
	int cnt = 0;
	for(int i=(L%K);i<=K+(R%K);i++)
		cnt += pref[i];
	if(cnt == 0) {
		int mnVal = 0;
		for(int i=0;i<20;i++)
			mnVal |= (rec[2*(2*K+1)+i] << i);
		return mnVal;
	}
	if(ord[cnt-1]) {
		int pos;
		for(int i=(L%K);i<=K+(R%K);i++)
			if(pref[i])
				pos = i;
		return (pos - K) + K * (R / K);
	}
	int pos;
	for(int i=K+(R%K);i>=L;i--)
		if(pref[i])
			pos = i;
	return pos + K * (L / K);
}

Bruno

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

namespace {
	const int K = 1384;
	int N;
	vector<int> P;
	vector<bool> rec;
	int cnt = 0;
	void sendBin(int x, int b) {
		for(int i=0;i<b;i++)
			SendB(x&(1<<i));
	}
	void sendPerm(vector<int> V) {
		stack<int> s;
		int cnt = 0;
		for(auto i: V) {
			while(s.size() && s.top() > i) {
				s.pop();
				SendB(0);
				cnt++;
			}
			SendB(1);
			cnt++;
			s.push(i);
		}
		for(;cnt<2*int(V.size());cnt++)
			SendB(1);
	}
	void toBin(vector<int> t) {
		assert(t.size() == 2 * K);
		vector<int> ans(4388);
		for(int i=0;i<4388;i++)
			for(int j=2*K;j--;) {
				if(t[j] & 1)
					(j?t[j-1]:ans[i]) += 3;
				t[j] /= 2;
			}
		for(int i=0;i<4388;i++)
			SendB(ans[i]);
	}
	vector<int> enc(vector<bool> a, vector<bool> b) {
		int c = 0;
		vector<int> v;
		for(auto i: a) {
			if(i)
				v.push_back(b[c++]?2:1);
			else
				v.push_back(0);
		}
		return v;
	}
}

void InitB(int N, std::vector<int> P) {
	while(P.size() % K)
		P.push_back(N++);
	::N = N;
	::P = P;
}

void ReceiveB(bool y) {
	rec.push_back(y);
	if(int(rec.size()) < 18)
		return;
	int X = 0;
	for(int i=0;i<18;i++)
		X += (rec[i] << i);
	int B = 0;
	while(B * (B + 1) / 2 <= X)
		B++;
	B--;
	int A = X - (B * (B + 1) / 2);
	if(A == B)
		sendPerm(vector<int>(P.begin()+A*K,P.begin()+(A+1)*K));
	else {
		vector<int> impt;
		for(int i=0;i<K;i++)
			impt.push_back(P[A*K+i]);
		int mnPt, mnVal;
		if(B == A + 1)
			mnVal = 1e9, mnPt = 0;
		else {
			mnPt = min_element(P.begin()+(A+1)*K,P.begin()+B*K) - P.begin();
			mnVal = P[mnPt];
		}
		impt.push_back(mnVal);
		for(int i=0;i<K;i++)
			impt.push_back(P[B*K+i]);
		vector<bool> pref(2*K), ord;
		vector<int> pl, pr;
		int curMn = mnVal;
		for(int i=K;i--;) {
			pref[i] = (impt[i] < curMn);
			curMn = min(impt[i], curMn);
			pl.push_back(i);
		}
		curMn = mnVal;
		for(int i=K+1;i<=2*K;i++) {
			pref[i] = (impt[i] < curMn);
			curMn = min(impt[i], curMn);
			pr.push_back(i);
		}
		int ptr = 0;
		for(auto i: pl) {
			while(ptr < int(pr.size()) && impt[pr[ptr]] > impt[i]) {
				ord.push_back(1);
				ptr++;
			}
			ord.push_back(0);
		}
		while(ptr < pr.size()) {
			ord.push_back(1);
			ptr++;
		}
		sendPerm(enc(pref, ord));
		sendBin(mnPt,20);
	}
}

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