Submission #1182959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182959		kl0989e	Flight to the Ford (BOI22_communication)	C++20	100 / 100	1126 ms	3308 KiB

communication

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

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

struct interval {
	int l, r;

	int sze() {
		return r-l+1;
	}
	bool in(int a) {
		return (l<=a && a<=r);
	}
};

void encode(int n, int x) {
	vector<interval> ok={{1,n}},nok;
	int oksze=n,noksze=0;
	while (oksze+noksze>4) {
		vector<interval> oka,okb,noka,nokb;
		int okasze=0,okbsze=0,nokasze=0,nokbsze=0;
		bool a=0;
		for (int i=0; i<ok.size(); i++) {
			if (okasze+ok[i].sze()<=oksze/2) {
				oka.pb(ok[i]);
				okasze+=oka.back().sze();
			}
			else if (okasze<oksze/2) {
				oka.pb({ok[i].l,ok[i].l+oksze/2-okasze-1});
				okb.pb({ok[i].l+oksze/2-okasze,ok[i].r});
				okasze+=oka.back().sze();
				okbsze+=okb.back().sze();
			}
			else {
				okb.pb({ok[i]});
				okbsze+=okb.back().sze();
			}
			if (oka.size()) {
				a|=(oka.back().in(x));
			}
		}
		for (int i=0; i<nok.size(); i++) {
			if (nokasze+nok[i].sze()<=noksze/2) {
				noka.pb(nok[i]);
				nokasze+=noka.back().sze();
			}
			else if (nokasze<=noksze/2) {
				noka.pb({nok[i].l,nok[i].l+noksze/2-nokasze-1});
				nokb.pb({nok[i].l+noksze/2-nokasze,nok[i].r});
				nokasze+=noka.back().sze();
				nokbsze+=nokb.back().sze();
			}
			else {
				nokb.pb({nok[i]});
				nokbsze+=nokb.back().sze();
			}
			if (noka.size()) {
				a|=(noka.back().in(x));
			}
		}
		bool ret=send(a);
		ok.clear();
		if (ret==0) {
			for (auto aa:okb) {
				ok.pb(aa);
			}
			for (auto aa:nokb) {
				ok.pb(aa);
			}
			nok=oka;
			oksze=okbsze+nokbsze;
			noksze=okasze;
		}
		else {
			for (auto aa:oka) {
				ok.pb(aa);
			}
			for (auto aa:noka) {
				ok.pb(aa);
			}
			nok=okb;
			oksze=okasze+nokasze;
			noksze=okbsze;
		}
	}
	vi nums;
	for (auto aa:ok) {
		for (int i=aa.l; i<=aa.r; i++) {
			nums.pb(i);
		}
	}
	for (auto aa:nok) {
		for (int i=aa.l; i<=aa.r; i++) {
			nums.pb(i);
		}
	}
	if (nums.size()<3) {
		return;
	}
	if (x==nums[0]) {
		send(0);send(0);send(0);send(0);
	}
	else if (x==nums[1]) {
		send(0);send(1);send(1);send(0);
	}
	else if (x==nums[2]) {
		send(1);send(0);send(0);send(1);
	}
	else {
		send(1);send(1);send(1);send(1);
	}
}

vi nums={0b0000,0b0110,0b1001,0b1111};

set<int> valid={0b0000,0b0001,0b0010,0b0100,0b0101,0b1000,0b1001,0b1010};

pi get(int a) {
	pi ret={-1,-1};
	for (int i=0; i<4; i++) {
		if (valid.count(a^nums[i])) {
			if (ret.fi==-1) {
				ret.fi=i;
			}
			else {
				ret.se=i;
			}
		}
	}
	return ret;
}

pi decode(int n) {
	vector<interval> ok={{1,n}},nok;
	int oksze=n,noksze=0;
	while (oksze+noksze>4) {
		vector<interval> oka,okb,noka,nokb;
		int okasze=0,okbsze=0,nokasze=0,nokbsze=0;
		for (int i=0; i<ok.size(); i++) {
			if (okasze+ok[i].sze()<=oksze/2) {
				oka.pb(ok[i]);
				okasze+=oka.back().sze();
			}
			else if (okasze<oksze/2) {
				oka.pb({ok[i].l,ok[i].l+oksze/2-okasze-1});
				okb.pb({ok[i].l+oksze/2-okasze,ok[i].r});
				okasze+=oka.back().sze();
				okbsze+=okb.back().sze();
			}
			else {
				okb.pb({ok[i]});
				okbsze+=okb.back().sze();
			}
		}
		for (int i=0; i<nok.size(); i++) {
			if (nokasze+nok[i].sze()<=noksze/2) {
				noka.pb(nok[i]);
				nokasze+=noka.back().sze();
			}
			else if (nokasze<=noksze/2) {
				noka.pb({nok[i].l,nok[i].l+noksze/2-nokasze-1});
				nokb.pb({nok[i].l+noksze/2-nokasze,nok[i].r});
				nokasze+=noka.back().sze();
				nokbsze+=nokb.back().sze();
			}
			else {
				nokb.pb({nok[i]});
				nokbsze+=nokb.back().sze();
			}
		}
		bool ret=receive();
		ok.clear();
		if (ret==0) {
			for (auto aa:okb) {
				ok.pb(aa);
			}
			for (auto aa:nokb) {
				ok.pb(aa);
			}
			nok=oka;
			oksze=okbsze+nokbsze;
			noksze=okasze;
		}
		else {
			for (auto aa:oka) {
				ok.pb(aa);
			}
			for (auto aa:noka) {
				ok.pb(aa);
			}
			nok=okb;
			oksze=okasze+nokasze;
			noksze=okbsze;
		}
	}
	vi nums;
	for (auto aa:ok) {
		for (int i=aa.l; i<=aa.r; i++) {
			nums.pb(i);
		}
	}
	for (auto aa:nok) {
		for (int i=aa.l; i<=aa.r; i++) {
			nums.pb(i);
		}
	}
	if (nums.size()==1) {
		return {nums[0],nums[0]};
	}
	if (nums.size()==2) {
		return {nums[0],nums[1]};
	}
	int t=receive()*8+receive()*4+receive()*2+receive();
	pi temp=get(t);
	return {nums[min(temp.fi,(int)nums.size()-1)],nums[min(temp.se,(int)nums.size()-1)]};
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85