Submission #591707

#	Time	Username	Problem	Language	Result	Execution time	Memory
591707		tutis	Flight to the Ford (BOI22_communication)	C++17	88 / 100	3235 ms	2048 KiB

communication

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int prob = 1;
#include "communication.h"
int dec3(int x)//4 bit x
{
	vector<int>ger;
	for (int m = 0; m < 16; m++)
	{
		bool ok = true;
		int v = m;
		while (v != 0)
		{
			if (v % 4 == 3)
				ok = false;
			v /= 2;
		}
		if (ok)
			ger.push_back(m);
	}
	int V[4] = {0, 0, 6, 9};
	for (int i = 1; i <= 3; i++)
	{
		bool ok = true;
		for (int j : ger)
			if (x == (V[i] ^ j))
				ok = false;
		if (ok)
			return i;
	}
	assert(false);
	return 0;
}
int enc3(int X)
{
	int v = 0;
	if (X == 1)
		v = 0;
	else if (X == 2)
		v = 6;
	else if (X == 3)
		v = 9;
	int val = 0;
	for (int t = 0; t < 4; t++)
	{
		val += send(v % 2) << t;
		v /= 2;
	}
	return dec3(val);
}
string S4[4] = {"1000",
                "0001",
                "1110",
                "0111"
               };
int conv4(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S4[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}
bitset<4> dec4(int x)//4 bit x
{
	vector<int>ger;
	for (int m = 0; m < 16; m++)
	{
		bool ok = true;
		int v = m;
		while (v != 0)
		{
			if (v % 4 == 3)
				ok = false;
			v /= 2;
		}
		if (ok)
			ger.push_back(m);
	}
	bitset<4>ret;
	for (int i = 0; i < 4; i++)
	{
		for (int j : ger)
			if (x == (conv4(i) ^ j))
				ret[i] = true;
	}
	return ret;
}
bitset<4> enc4(int X)
{
	int v = conv4(X);
	int val = 0;
	for (int t = 0; t < 4; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	auto ret = dec4(val);
	assert(ret[X] == true);
	return ret;
}
const int bitcnt = 29;
int bitcnt1 = 14;
int encB(int v)
{
	int val = 0;
	for (int t = 0; t < bitcnt1; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	return val;
}
int C[40][2];
bool prec = false;
int getL(int l)
{
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	return C[l][0] + C[l][1];
}
int cntT(int m, int l, int g, int x = 0)
{
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	if (m == (1 << l))
	{
		return C[l][0] + C[l][1];
	}
	int ret = 0;
	for (int b = l; b >= 1; b--)
	{
		int vv = m & (1 << (b - 1));
		int gg = g & (1 << (b - 1));
		m -= vv;
		g -= gg;
		vv /= (1 << (b - 1));
		gg /= (1 << (b - 1));
		int f1 = -1;
		for (int nxt : {0, 1}) {
			int f = gg ^ nxt;
			if (f == 1 && x == 1)
				continue;
			if (nxt < vv)
				ret += C[b][f];
			else if (nxt == vv)
				f1 = f;
		}
		if (f1 == -1)
			break;
		x = f1;
	}
	return ret;
}
int kth(int k, int l, int g, int x = 0)
{
	if (l == 0)
		return 0;
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	int s = 0;
	for (int b = l; b >= 1; b--)
	{
		int gg = g & (1 << (b - 1));
		g -= gg;
		gg /= (1 << (b - 1));
		for (int nxt : {0, 1})
		{
			int f = gg ^ nxt;
			if (f == 1 && x == 1)
				continue;
			if (k < C[b][f])
			{
				s += ((1 << (b - 1)) * nxt);
				x = f;
				break;
			}
			else
				k -= C[b][f];
		}
	}
	return s;
}
void encode(int N, int X)
{
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	for (int bc = bitcnt; bc >= 5; bc--)
		if (N >= (1 << bc))
		{
			int v = N / (1 << bc);
			int k1 = N % (1 << bc);
			int k0 = (1 << bc) - k1;
			assert(k0 * v + k1 * (v + 1) == N);
			int vv = (X - 1) / v;
			if (vv >= k0)
				vv = k0 + (X - k0 * v - 1) / (v + 1);
			assert(X >= 1 && X <= N);
			assert(vv >= 0 && vv < (1 << bc));

			bitcnt1 = bc;
			int gal1 = encB(vv);
			int c1 = getL(bc);
			int kk0 = cntT(k0, bc, gal1);
			int s = (v + 1) * c1 - kk0;
			int c = cntT(vv, bc, gal1);
			if (X <= k0 * v + v + 1)
			{
				X -= (vv - c) * v;
			}
			else
			{
				X -= vv * (v + 1) - k0;
				X += c * (v + 1) - kk0;
			}
			encode(s, X);
			return;
		}
	if (N >= 4)
	{
		int sz[4];
		for (int i = 0; i < 4; i++)
			sz[i] = N / 4;
		for (int i = 0; i < (N % 4); i++)
			sz[i]++;
		int vv = 0;
		{
			int XX = X;
			while (XX > sz[vv])
			{
				XX -= sz[vv];
				vv++;
			}
		}
		bitset<4>gal = enc4(vv);
		int s = 0;
		for (int i = 0; i < 4; i++)
		{
			if (gal[i])
			{
				s += sz[i];
			}
			else if (i < vv)
				X -= sz[i];
		}
		encode(s, X);
		return;
	}
}
pair<int, int> decode(int N)
{
	if (N == 1)
		return {1, 1};
	if (N == 2)
		return {1, 2};
	if (N == 3)
	{
		int val = 0;
		for (int t = 0; t < 4; t++)
			val += receive() << t;
		int v = dec3(val);
		pair<int, int>ans = {1, 2};
		if (v == 1)
			ans.first = 3;
		if (v == 2)
			ans.second = 3;
		return ans;
	}
	for (int bc = bitcnt; bc >= 5; bc--)
		if (N >= (1 << bc))
		{
			int re = 0;
			for (int t = 0; t < bc; t++)
				re += receive() << t;
			int v = N / (1 << bc);
			int k1 = N % (1 << bc);
			int k0 = (1 << bc) - k1;

			int c1 = getL(bc);
			int kk0 = cntT(k0, bc, re);
			int s = (v + 1) * c1 - kk0;

			pair<int, int>r = decode(s);

			auto blo = [&](int p)->int
			{
				int i = (p - 1) / v;
				if (i >= kk0)
					i = kk0 + (p - kk0 * v - 1) / (v + 1);
				return i;
			};
			int i1 = kth(blo(r.first), bc, re);
			int i2 = kth(blo(r.second), bc, re);
			if (i1 <= k0)
				r.first += v * (i1 - cntT(i1, bc, re));
			else
			{
				r.first += (k0 - kk0) * v;
				r.first += (v + 1) * (i1 - cntT(i1, bc, re) - (k0 - kk0));
			}
			if (i2 <= k0)
				r.second += v * (i2 - cntT(i2, bc, re));
			else
			{
				r.second += (k0 - kk0) * v;
				r.second += (v + 1) * (i2 - cntT(i2, bc, re) - (k0 - kk0));
			}
			return r;
		}
	if (N >= 4)
	{
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		bitset<4> gal = dec4(re);
		int sz[4];
		for (int i = 0; i < 4; i++)
			sz[i] = N / 4;
		for (int i = 0; i < (N % 4); i++)
			sz[i]++;
		int s = 0;
		for (int i = 0; i < 4; i++)
			if (gal[i])
				s += sz[i];
		pair<int, int>r = decode(s);
		int sum = 0;
		bool ger1 = false;
		bool ger2 = false;
		for (int i = 0; i < 4; i++)
		{
			if (gal[i])
			{
				if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
				{
					for (int j = 0; j < i; j++)
						if (gal[j] == false)
							r.first += sz[j];
					ger1 = true;
				}
				if (r.second > sum && r.second <= sum + sz[i] && ger2 == false)
				{
					for (int j = 0; j < i; j++)
						if (gal[j] == false)
							r.second += sz[j];
					ger2 = true;
				}
				sum += sz[i];
			}
		}
		return r;
	}
	return { -1, -1};
}
// int main()
// {
// 	mt19937 rng(0);
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 189189;
// 		int val = (rng() % N) + 1;
// 		encode(N, val);
// 		pair<int, int>v = decode(N);
// 		cout << v.first << " " << v.second << endl;
// 		assert(v.first == val || v.second == val);
// 	}
// }

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