Submission #591999

#	Time	Username	Problem	Language	Result	Execution time	Memory
591999		tutis	Flight to the Ford (BOI22_communication)	C++17	15 / 100	7756 ms	118784 KiB

communication

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int prob = 500;
#include "communication.h"
struct intervalset
{
	int sz = 0;
	vector<pair<int, int>>S;//sorted, disjoint
	intervalset()
	{

	}
	intervalset(int N)
	{
		sz = N;
		S.push_back({1, N});
	}
	void append(pair<int, int> v)
	{
		sz += v.second - v.first + 1;
		if (S.empty())
			S.push_back(v);
		else {
			if (v.first > S.back().second)
			{
				if (v.first == S.back().second + 1)
					S.back().second = v.second;
				else
					S.push_back(v);
			}
			else
			{
				assert(v.first >= S.back().first);
				if (v.second > S.back().second) {
					sz -= S.back().second - v.first + 1;
					S.back().second = v.second;
				}
			}
		}
	}
	pair<intervalset, intervalset> split(int k)
	{	//k,sz-k
		intervalset A;
		intervalset B;
		for (pair<int, int>i : S)
		{
			if (i.second - i.first + 1 <= k)
			{
				A.append(i);
				k -= i.second - i.first + 1;
			}
			else if (k <= 0)
			{
				B.append(i);
			}
			else
			{
				A.append({i.first, i.first + k - 1});
				B.append({i.first + k, i.second});
				k = 0;
			}
		}
		return {A, B};
	}
	int kth(int k)
	{
		for (pair<int, int>i : S)
		{
			if (i.second - i.first + 1 < k)
			{
				k -= i.second - i.first + 1;
			}
			else
			{
				return i.first + (k - 1);
			}
		}
		assert(false);
		return 0;
	}
	int kelintas(int x)
	{
		int r = 0;
		for (pair<int, int>i : S)
		{
			if (i.second < x)
				r += (i.second - i.first + 1);
			else if (x < i.first)
				return 0;
			else
				return r + (x - i.first + 1);
		}
		return 0;
	}
	intervalset(const intervalset &A, const intervalset &B)
	{
		const vector<pair<int, int>>&a = A.S;
		const vector<pair<int, int>>&b = B.S;
		int i = 0;
		int j = 0;
		while (i < (int)a.size() && j < (int)b.size())
		{
			if (a[i].first < b[j].first)
				append(a[i++]);
			else
				append(b[j++]);
		}
		while (i < (int)a.size())
			append(a[i++]);
		while (j < (int)b.size())
			append(b[j++]);
	}
};
const int mxsum = 300;
pair<int, pair<int, int>> K[mxsum][mxsum];
bool prec = false;
map<pair<int, int>, pair<int, pair<int, int>>>M;
pair<int, pair<int, int>> getbest(int A, int B)
{
	if (A + B < mxsum)
	{
		if (prec == false)
		{
			prec = true;
			for (int sum = 0; sum < mxsum; sum++)
				for (int a = 0; a <= sum; a++)
				{
					int b = sum - a;
					K[a][b] = {1000, {0, 0}};
				}
			for (int sum = 0; sum < mxsum; sum++)
			{
				if (sum <= 2)
				{
					for (int a = 0; a <= sum; a++) {
						int b = sum - a;
						K[a][b] = {0, {0, 0}};
					}
				}
				else {
					bool rep = true;
					while (rep)
					{
						rep = false;
						for (int a = 0; a <= sum; a++)
						{
							int b = sum - a;

							for (int a0 = 0; a0 <= a; a0++)
							{
								for (int b0 = 0; b0 <= b; b0++)
								{
									int a1 = a - a0;
									int b1 = b - b0;

									int a_ = a0 + b0;
									int b_ = a1;

									int a__ = a1 + b1;
									int b__ = a0;
									int g = 1 + max(K[a_][b_].first, K[a__][b__].first);
									if (K[a][b].first > g)
									{
										K[a][b] = {g, {a0, b0}};
										rep = true;
									}
								}
							}
						}
					}
				}
			}
		}
		return K[A][B];
	}
	else
	{
		if (M.count({A, B}))
			return M[ {A, B}];
		pair<int, pair<int, int>> &bst = M[ {A, B}];
		bst = {1000, {0, 0}};
		auto check = [&](int a0, int b0)
		{
			if (a0 < 0 || a0 > A || b0 < 0 || b0 > B)
				return;
			int b1 = B - b0;
			int a1 = A - a0;
			int a_ = a0 + b0;
			int b_ = a1;
			int a__ = a1 + b1;
			int b__ = a0;
			int g = 1 + max(getbest(a_, b_).first, getbest(a__, b__).first);
			if (bst.first > g)
				bst = {g, {a0, b0}};
		};
		for (int da = 0; da <= 1; da++)
		{
			for (int db = 0; db <= da; db++)
				for (int wa : { -1, 1})
					for (int wb : { -1, 1})
						check(A / 2 + wa * da, B / 2 + wb * db);
		}
		return bst;
	}
}
vector<pair<int, int>>eil;
void encode(int N, int X)
{
	intervalset A(N);
	intervalset B;
	mt19937 rng(0);
	while (A.sz + B.sz > 2)
	{
		eil.push_back({A.sz, B.sz});
		pair<int, int>c = getbest(A.sz, B.sz).second;
		int a0 = c.first;
		int b0 = c.second;
		eil.push_back({a0, b0});
		eil.push_back({0, 0});
		intervalset C(A, B);
		int ka = A.kelintas(X);
		int kb = B.kelintas(X);
		int s = 1;
		if (ka != 0 && ka <= a0)
			s = 0;
		if (kb != 0 && kb <= b0)
			s = 0;
		pair<intervalset, intervalset>A_ = A.split(a0);
		pair<intervalset, intervalset>B_ = B.split(b0);
		int r = send(s);
		if (r == 0)
		{
			A = intervalset(A_.first, B_.first);
			B = A_.second;
		}
		else
		{
			A = intervalset(A_.second, B_.second);
			B = A_.first;
		}
	}
}
pair<int, int> decode(int N)
{
	intervalset A(N);
	intervalset B;
	mt19937 rng(0);
	while (A.sz + B.sz > 2)
	{
		pair<int, int>c = getbest(A.sz, B.sz).second;
		int a0 = c.first;
		int b0 = c.second;
		pair<intervalset, intervalset>A_ = A.split(a0);
		pair<intervalset, intervalset>B_ = B.split(b0);
		int r = receive();
		if (r == 0)
		{
			A = intervalset(A_.first, B_.first);
			B = A_.second;
		}
		else
		{
			A = intervalset(A_.second, B_.second);
			B = A_.first;
		}
	}
	if (A.sz == 0)
		return {B.S[0].first, B.S.back().second};
	if (B.sz == 0)
		return {A.S[0].first, A.S.back().second};
	return {A.S[0].first, B.S[0].first};
}
// int main()
// {
// 	int mx = 0;
// 	vector<pair<int, int>>ilg;
// 	for (int test = 0; test < 100; test++)
// 	{
// 		int N = 3 + asdasdasdasdasd() % ((int)1e9 - 3 + 1);
// 		int X = (asdasdasdasdasd() % N) + 1;
// 		encode(N, X);
// 		pair<int, int>a = decode(N);
// 		assert(a.first >= 1 && a.first <= N && a.second >= 1 && a.second <= N);
// 		assert(a.first == X || a.second == X);
// 		if (kiekis > mx)
// 		{
// 			ilg = eil;
// 			mx = kiekis;
// 		}
// 		if (test % 10 == 0)
// 			cout << kiekis << endl;
// 		kiekis = 0;
// 		eil.clear();
// 	}
// }

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