Submission #1209557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209557		emptypringlescan	Shopping (JOI21_shopping)	C++17	0 / 100	78 ms	16292 KiB

Anna

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

namespace {

int N, L, R;
int count;
vector<int> recv;
int buc=512,sz=1954;
int bl,br;
}  // namespace

void InitA(int N, int L, int R) {
  ::N = N;
  ::L = L;
  ::R = R;
  bl=L/sz,br=R/sz;
  for(int i=0; i<9; i++) SendA((bl>>i)&1);
  for(int i=0; i<9; i++) SendA((br>>i)&1);
}

void ReceiveA(bool x) {
	if(x) recv.push_back(1);
	else recv.push_back(0);
}

int Answer() {
	int yay=0;
	for(int i=0; i<20; i++) if(recv[i]) yay^=(1<<i);
	//cout << "yay " << yay << '\n';
	vector<int> lf,rg;
	for(int i=0; i<sz; i++){
		if(recv[20+i]) lf.push_back(bl*sz+sz-1-i);
	}
	for(int i=0; i<sz; i++){
		if(recv[20+sz+i]) rg.push_back(br*sz+i);
	}
	int ret=yay;
	int c1=0,c2=0;
	for(int i=0; i<(int)lf.size()+(int)rg.size(); i++){
		if(recv[20+sz+sz+i]==0){
			if(lf[c1]>=L&&lf[c1]<=R) ret=lf[c1];
			c1++;
		}
		else{
			if(rg[c2]<=R&&rg[c2]>=L) ret=rg[c2];
			c2++;
		}
	}
	return ret;
}

Bruno

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

int N;
int arr[2000000];
int cn;
int buc=512,sz=1954;
vector<int> recv;
}  // namespace

void InitB(int N, std::vector<int> P) {
  ::N = N;
  for(int i = 0; i < N; i++) {
    arr[i] = P[i];
  }
  for(int i=N; i<2000000; i++) arr[i]=(1<<20)-1;
  cn = 0;
}

void ReceiveB(bool y) {
	cn++;
	if(y) recv.push_back(1);
	else recv.push_back(0);
	if(cn==18){
		int bl=0,br=0;
		for(int i=0; i<9; i++) if(recv[i]) bl^=(1<<i);
		for(int i=0; i<9; i++) if(recv[i+9]) br^=(1<<i);
		pair<int,int> mn={(1<<20)-1,-1};
		for(int i=bl*sz+sz; i<br*sz; i++) mn=min(mn,{arr[i],i});
		int c1=bl*sz+sz-1,c2=br*sz;
		for(int i=0; i<20; i++) SendB((mn.second>>i)&1);
		int cmn=mn.first;
		vector<int> lf,rg;
		for(int i=c1; i>=bl*sz; i--){
			if(arr[i]<cmn){
				SendB(true);
				cmn=arr[i];
				lf.push_back(i);
			}
			else SendB(false);
		}
		cmn=mn.first;
		for(int i=c2; i<br*sz+sz; i++){
			if(arr[i]<cmn){
				SendB(true);
				cmn=arr[i];
				rg.push_back(i);
			}
			else SendB(false);
		}
		c1=0,c2=0;
		while(c1<(int)lf.size()||c2<(int)rg.size()){
			if(c1==(int)lf.size()) SendB(1),c2++;
			else if(c2==(int)rg.size()) SendB(0),c1++;
			else if(arr[lf[c1]]<arr[rg[c2]]) SendB(1),c2++;
			else SendB(0),c1++;
		}
	}
}

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