Submission #1134152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134152		PagodePaiva	Flight to the Ford (BOI22_communication)	C++20	0 / 100	155 ms	31104 KiB

communication

#include<bits/stdc++.h>
#include"communication.h"
#define recieve receive

using namespace std;

struct Node{
	Node *lf, *rf;
	int val, lz;
	Node(int v, int ll, int rr){
		val = (rr-ll+1)*v;
		lz = -1;
		lf = rf = NULL;
	}
	void unlazy(int l, int r){
		if(lz==-1) return;
		val = lz*(r-l+1);
		if(l != r){
			int mid = (l+r)/2;
			if(!lf) lf = new Node(1, l, mid);
			if(!rf) rf = new Node(1, mid+1, r);
			lf->lz = lz;
			rf->lz = lz;
		}
		lz = -1;
	}
	void update(int l, int r, int tl, int tr, int v){
		unlazy(tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lz = v;
			unlazy(tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		if(!lf) lf = new Node(1, tl, mid);
		if(!rf) rf = new Node(1, mid+1, tr);
		lf->update(l, r, tl, mid, v);
		rf->update(l, r, mid+1, tr, v);
		val = lf->val+rf->val;
		return;
	}
	int query(int l, int r, int tl, int tr){
		unlazy(tl, tr);
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return val;
		int mid = (tl+tr)/2;
		if(!lf) lf = new Node(1, tl, mid);
		if(!rf) rf = new Node(1, mid+1, tr);
		return lf->query(l, r, tl, mid)+rf->query(l, r, mid+1, tr);
	}
	int busca(int l, int r, int v){
		unlazy(l, r);
		if(l == r) return l;
		int mid = (l+r)/2;
		if(!lf) lf = new Node(1, l, mid);
		if(lf->val >= v) return lf->busca(l, mid, v);
		else{
			v -= lf->val;
			if(!rf) rf = new Node(1, mid+1, r);
			return rf->busca(mid+1, r, v);
		}
	}
};

void encode(int n, int x) {
	Node seg(1, 1, n);
	while(seg.query(1, n, 1, n) > 2){
		int tot = seg.query(1, n, 1, n);
		int m1 = tot/3, m2 = 2*tot/3;
		int l = 1, p1 = seg.busca(1, n, m1), p2 = seg.busca(1, n, m2), r = n;
		//cout << tot << ' ' << l << ' ' << p1 << ' ' << p2 << ' ' << r << endl;
		if(l <= x and x <= p2){
			int t = send(1);
			if(t == 1){
				t = send(1);
				if(t == 1){
					seg.update(p2+1, n, 1, n, 0);
					continue;
				}
			}
		}
		else{
			int t = send(0);
			if(t == 1) send(0);
		}
		int a, b;
		if(p1 < x and x <= p2){
			a = send(1);
		}
		else{
			a = send(0);
		}
		if(p1 < x and x <= p2){
			b = send(0);
		}
		else{
			b = send(1);
		}
		if(a == 0 and b == 0){
			seg.update(p1+1, n, 1, n, 0);
		}
		else if(a == 0 and b == 1){
			seg.update(p1+1, p2, 1, n, 0);
		}
		else if(a == 1 and b == 0){
			seg.update(1, p1, 1, n, 0);
		}
		else{
			seg.update(1, p1, 1, n, 0);
		}
	}
	return;
}

std::pair<int, int> decode(int n) {
	Node seg(1, 1, n);
	while(seg.query(1, n, 1, n) > 2){
		int tot = seg.query(1, n, 1, n);
		int m1 = tot/3, m2 = 2*tot/3;
		int l = 1, p1 = seg.busca(1, n, m1), p2 = seg.busca(1, n, m2), r = n;
		int x = recieve();
		if(x == 1){
			x = recieve();
			if(x == 1){
				seg.update(p2+1, n, 1, n, 0);
				continue;
			}
		}
		int a = recieve();
		int b = recieve();
		if(a == 0 and b == 0){
			seg.update(p1+1, n, 1, n, 0);
		}
		else if(a == 0 and b == 1){
			seg.update(p1+1, p2, 1, n, 0);
		}
		else if(a == 1 and b == 0){
			seg.update(1, p1, 1, n, 0);
		}
		else{
			seg.update(1, p1, 1, n, 0);
		}
	}
	cout << seg.busca(1, n, 1) << ' ' << seg.busca(1, n, 2) << endl;
	return {seg.busca(1, n, 1), seg.busca(1, n, 2)};
}

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