Submission #1134178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134178		PagodePaiva	Flight to the Ford (BOI22_communication)	C++20	15 / 100	137 ms	6040 KiB

communication

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

using namespace std;

const int N = 20010;

struct Segtree{
	int tree[4*N], lazy[4*N], lf[4*N], rf[4*N];
	int nx;
	void build(int val, int l, int r){
		memset(lazy, -1, sizeof lazy);
		memset(lf, -1, sizeof lf);
		memset(rf, -1, sizeof rf);
		tree[1] = (r-l+1);
		nx = 2;
	}
	void unlazy(int node, int l, int r){
		if(lazy[node] == -1) return;
		tree[node] = (r-l+1)*lazy[node];
		if(l != r){
			int mid = (l+r)/2;
			if(lf[node] == -1){
				lf[node] = nx;
				nx++;
				tree[lf[node]] = (mid-l+1);
			}
			if(rf[node] == -1){
				rf[node] = nx;
				nx++;
				tree[rf[node]] = r-mid;
			}
			lazy[lf[node]] = lazy[rf[node]] = lazy[node];
		}
		lazy[node] = -1;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] = val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		if(lf[node] == -1){
			lf[node] = nx;
			nx++;
			tree[lf[node]] = (mid-tl+1);
			lazy[lf[node]] = -1;
		}
		if(rf[node] == -1){
			rf[node] = nx;
			nx++;
			tree[rf[node]] = tr-mid;
			lazy[rf[node]] = -1;
		}
		update(lf[node], l, r, tl, mid, val);
		update(rf[node], l, r, mid+1, tr, val);
		tree[node] = tree[lf[node]]+tree[rf[node]];
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 0;
			return tree[node];
	}
	int busca(int node, int l, int r,int val){
		unlazy(node, l, r);
		if(l == r) return l;
		int mid = (l+r)/2;
		if(lf[node] == -1){
			lf[node] = nx;
			nx++;
			tree[lf[node]] = mid-l+1;
			lazy[lf[node]] = -1;
		}
		if(tree[lf[node]]>= val) return busca(lf[node], l, mid, val);
		if(rf[node] == -1){
			rf[node] = nx;
			nx++;
			tree[rf[node]] = r-mid;
			lazy[rf[node]] = -1;
		}
		return busca(rf[node], mid+1, r, val-tree[lf[node]]);
	}
} seg;

void encode(int n, int x) {
	seg.build(1, 1, n);
	while(seg.query(1, 1, n, 1, n) > 2){
		int tot = seg.query(1, 1, n, 1, n);
		int p1 = seg.busca(1, 1, n, (tot <= 4 ? tot/3 : tot/2)), p2 = seg.busca(1, 1, n, (tot <= 4 ? 2*tot/3 : (3*tot)/4));
		if(x <= p1){
			int t = send(1);
			if(t == 0) send(1);
		}
		else{
			int t = send(0);
			if(t == 0){
				t = send(0);
				if(t == 0){
					seg.update(1, 1, p1, 1, n, 0);
					continue;
				}
			}
		}
		int t;
		if(p1 < x and x <= p2){
			t = send(1);
		}
		else{
			t = send(0);
		}
		if(t == 1){
			seg.update(1, p2+1, n, 1, n, 0);
		}
		else{
			seg.update(1, p1+1, p2, 1, n, 0);
		}
	}
	return;
}

std::pair<int, int> decode(int n) {
	seg.build(1, 1, n);
	while(seg.query(1, 1, n, 1, n) > 2){
		int tot = seg.query(1, 1, n, 1, n);
		int p1 = seg.busca(1, 1, n, (tot <= 4 ? tot/3 : tot/2)), p2 = seg.busca(1, 1, n, (tot <= 4 ? 2*tot/3 : (3*tot)/4));
		int t = recieve();
		if(t == 0){
			t = recieve();
			if(t == 0){
				seg.update(1,1, p1, 1, n, 0);
				continue;
			}
		}
		t = recieve();
		if(t == 1){
			seg.update(1, p2+1, n, 1, n, 0);
		}
		else{
			seg.update(1, p1+1, p2, 1, n, 0);
		}
	}
	return {seg.busca(1, 1, n, 1), seg.busca(1, 1, n, 2)};
}

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