Submission #590940

#	Time	Username	Problem	Language	Result	Execution time	Memory
590940		tutis	Flight to the Ford (BOI22_communication)	C++17	57 / 100	3772 ms	2056 KiB

communication

#include <bits/stdc++.h>
using namespace std;
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 S6[6] = {"00000",
                "00001",
                "00110",
                "01111",
                "10010",
                "11111"
               };
string S8[8] = {"000000",
                "000010",
                "011001",
                "011011",
                "100100",
                "100110",
                "111101",
                "111111",
               };
int conv6(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S6[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}
int conv8(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S8[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}

bitset<8> dec8(int x)//6 bit x
{
	vector<int>ger;
	for (int m = 0; m < 64; 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<8>ret;
	for (int i = 0; i < 8; i++)
	{
		for (int j : ger)
			if (x == (conv8(i) ^ j))
				ret[i] = true;
	}
	return ret;
}
bitset<6> dec6(int x)//5 bit x
{
	vector<int>ger;
	for (int m = 0; m < 32; 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<6>ret;
	for (int i = 0; i < 6; i++)
	{
		for (int j : ger)
			if (x == (conv6(i) ^ j))
				ret[i] = true;
	}
	return ret;
}
bitset<8> enc8(int X)
{
	int v = conv8(X);
	int val = 0;
	for (int t = 0; t < 6; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	auto ret = dec8(val);
	assert(ret[X] == true);
	return ret;
}
bitset<6> enc6(int X)
{
	int v = conv6(X);
	int val = 0;
	for (int t = 0; t < 5; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	auto ret = dec6(val);
	assert(ret[X] == true);
	return ret;
}
void encode(int N, int X)
{
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	if (N >= 8)
	{
		int v = N / 8;
		int vv = (X - 1) / v;
		vv = min(vv, 7);
		bitset<8>gal = enc8(vv);
		int sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
		int s = 0;
		for (int i = 0; i < 8; i++)
		{
			if (gal[i])
			{
				s += sz[i];
			}
			else if (i < vv)
				X -= sz[i];
		}
		encode(s, X);
		return;
	}
	if (N >= 6)
	{
		int v = N / 6;
		int vv = (X - 1) / v;
		vv = min(vv, 5);
		bitset<6>gal = enc6(vv);
		int sz[6] = {v, v, v, v, v, N - 5 * v};
		int s = 0;
		for (int i = 0; i < 6; i++)
		{
			if (gal[i])
			{
				s += sz[i];
			}
			else if (i < vv)
				X -= sz[i];
		}
		encode(s, X);
		return;
	}
	int v = N / 3;
	int vv = 3;
	if (X <= v)
		vv = 1;
	else if (X <= 2 * v)
		vv = 2;
	int val = enc3(vv);
	assert(val != vv);
	if (val == 2)
	{
		if (vv == 1)
			encode(N - v, X);
		if (vv == 3)
			encode(N - v, X - v);
	}
	if (val == 1)
		encode(N - v, X - v);
	if (val == 3)
		encode(2 * v, X);
}
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;
	}
	else if (N >= 8)
	{
		int re = 0;
		for (int t = 0; t < 6; t++)
			re += receive() << t;
		bitset<8> gal = dec8(re);
		int v = N / 8;
		int sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
		int s = 0;
		for (int i = 0; i < 8; 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 < 8; 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;
	}
	else if (N >= 6)
	{
		int re = 0;
		for (int t = 0; t < 5; t++)
			re += receive() << t;
		bitset<6> gal = dec6(re);
		int v = N / 6;
		int sz[6] = {v, v, v, v, v, N - 5 * v};
		int s = 0;
		for (int i = 0; i < 6; 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 < 6; 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;
	}
	else
	{
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		int val = dec3(re);
		int v = N / 3;
		if (val == 2)
		{
			pair<int, int>r = decode(N - v);
			if (r.first > v)
				r.first += v;
			if (r.second > v)
				r.second += v;
			return r;
		}
		if (val == 1)
		{
			pair<int, int>r = decode(N - v);
			r.first += v;
			r.second += v;
			return r;
		}
		if (val == 3)
			return decode(2 * v);
	}
	return { -1, -1};
}
const int bitcnt = 5;
const int bitsz = 1 << bitcnt;
const int cnt2 = 5;
// int main()
// {
// 	// vector<int>ger;
// 	// for (int m = 0; m < bitsz; 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<bitsz>gal[bitsz];
// 	// for (int m = 0; m < bitsz; m++)
// 	// 	for (int v : ger)
// 	// 		gal[m][m ^ v] = true;
// 	// int v[15];
// 	// v[0] = 0;
// 	// int rec = 5000;
// 	// {
// 	// 	for (v[1] = v[0] + 1; v[1] < bitsz; v[1]++)
// 	// 	{
// 	// 		for (v[2] = v[1] + 1; v[2] < bitsz; v[2]++)
// 	// 		{
// 	// 			for (v[3] = v[2] + 1; v[3] < bitsz; v[3]++)
// 	// 			{
// 	// 				for (v[4] = v[3] + 1; v[4] < bitsz; v[4]++)
// 	// 				{
// 	// 					//for (v[5] = v[4] + 1; v[5] < bitsz; v[5]++)
// 	// 					{
// 	// 						//for (v[6] = v[5] + 1; v[6] < bitsz; v[6]++)
// 	// 						{
// 	// 							//for (v[7] = v[6] + 1; v[7] < bitsz; v[7]++)
// 	// 							{
// 	// 								int mx = 0;
// 	// 								for (int i = 0; i < cnt2; i++)
// 	// 								{
// 	// 									for (int m : ger)
// 	// 									{
// 	// 										int cnt = 0;
// 	// 										int rec = v[i] ^ m;
// 	// 										for (int t = 0; t < cnt2; t++)
// 	// 											if (gal[v[t]][rec])
// 	// 												cnt++;
// 	// 										mx = max(mx, cnt);
// 	// 									}
// 	// 								}
// 	// 								if (mx < rec)
// 	// 								{
// 	// 									cout << mx << endl;
// 	// 									for (int t = 0; t < cnt2; t++)
// 	// 										cout << bitset<bitcnt>(v[t]) << endl;
// 	// 									cout << endl;
// 	// 									rec = mx;
// 	// 								}
// 	// 							}
// 	// 						}
// 	// 					}
// 	// 				}
// 	// 			}
// 	// 		}
// 	// 	}
// 	// }
// 	// return 0;
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 8;
// 		int val = (t % 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: 42.00003 / 85