Submission #1209390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209390		PenguinsAreCute	Shopping (JOI21_shopping)	C++17	1 / 100	69 ms	12368 KiB

Anna

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

namespace {
	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 / 1384, B = R / 1384;
	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() {
		return (L / 1384) * 1384 + getMin(rec, L % 1384, R % 1384);
	/*
	vector<int> v;
	for(int i=0;i<int(rec.size());i+=14) {
		int cur = 0;
		for(int j=0;j<14;j++)
			cur |= (rec[i+j] << j);
		v.push_back(cur);
	}
	int res = 1e9;
	if((L / 20) == (R / 20)) {
		for(int i=(L/20);i<=(R/20);i++)
	}
	*/
}

Bruno

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

namespace {
	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() % 1384)
		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*1384,P.begin()+(A+1)*1384));
	else {} // TODO
}

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