Submission #1134162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134162		PagodePaiva	Flight to the Ford (BOI22_communication)	C++20	30 / 100	1907 ms	10572 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 m1 = tot/3, m2 = 2*tot/3;
		int l = 1, p1 = seg.busca(1, 1, n, m1), p2 = seg.busca(1, 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(1, 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 <= n){
			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(1, p1+1, n, 1, n, 0);
		}
		else if(a == 0 and b == 1){
			seg.update(1, p1+1, p2, 1, n, 0);
		}
		else if(a == 1 and b == 0){
			seg.update(1, 1, p1, 1, n, 0);
		}
		else{
			seg.update(1, 1, p1, 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 m1 = tot/3, m2 = 2*tot/3;
		int l = 1, p1 = seg.busca(1, 1, n, m1), p2 = seg.busca(1, 1, n, m2), r = n;
		int x = recieve();
		if(x == 1){
			x = recieve();
			if(x == 1){
				seg.update(1, p2+1, n, 1, n, 0);
				continue;
			}
		}
		int a = recieve();
		int b = recieve();
		if(a == 0 and b == 0){
			seg.update(1, p1+1, n, 1, n, 0);
		}
		else if(a == 0 and b == 1){
			seg.update(1, p1+1, p2, 1, n, 0);
		}
		else if(a == 1 and b == 0){
			seg.update(1, 1, p1, 1, n, 0);
		}
		else{
			seg.update(1, 1, p1, 1, n, 0);
		}
	}
	//cout << seg.busca(1, n, 1) << ' ' << seg.busca(1, n, 2) << endl;
	return {seg.busca(1, 1, n, 1), seg.busca(1, 1, n, 2)};
}

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