Submission #1209395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209395		PenguinsAreCute	Shopping (JOI21_shopping)	C++17	32 / 100	83 ms	12412 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);
	}
}

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);
	int mnPt = getMin(vector<bool>(rec.begin(),rec.begin()+2*(2*K+1)),L%K,(R%K)+K+1);
	if(mnPt < K)
		return mnPt + (L / K) * K;
	if(mnPt > K)
		return (mnPt - K - 1) + (R / K) * K;
	int mnVal = 0;
	for(int i=0;i<20;i++)
		mnVal |= (rec[2*(2*K+1)+i] << i);
	return mnVal;
}

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 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]);
		sendPerm(impt);
		sendBin(mnPt,20);
	}
}

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