Submission #590968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
590968	2022-07-06T16:10:15 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	74 / 100	3658 ms	2016 KB

communication

#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"
               };
string S6[6] = {"00000",
                "00001",
                "00110",
                "01111",
                "10010",
                "11111"
               };
string S8[8] = {"000000",
                "000010",
                "011001",
                "011011",
                "100100",
                "100110",
                "111101",
                "111111",
               };
int conv4(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S4[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}
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<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;
}
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 >= 4)
	{
		int v = N / 4;
		int vv = (X - 1) / v;
		vv = min(vv, 3);
		bitset<4>gal = enc4(vv);
		int sz[4] = {v, v, v, N - 3 * v};
		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;
	}
	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 >= 4)
	{
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		bitset<4> gal = dec4(re);
		int v = N / 4;
		int sz[4] = {v, v, v, N - 3 * v};
		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;
	}
	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 = 4;
const int bitsz = 1 << bitcnt;
const int cnt2 = 4;
// 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[100];
// 	// v[0] = 0;
// 	// int rec = 5000;
// 	// mt19937_64 rng(0);
// 	// for (int tst = 0; tst < 10000000; tst++) {
// 	// 	for (int i = 0; i < cnt2 / 2; i++)
// 	// 		v[i] = rng() % bitsz;
// 	// 	for (int i = cnt2 - 1; i >= cnt2 / 2; i--)
// 	// 		v[i] = v[cnt2 - 1 - i] ^ (bitsz - 1);
// 	// 	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)
// 	// 			break;
// 	// 	}
// 	// 	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 = 4;
// 		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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1812 KB	Output is correct
2	Correct	15 ms	1704 KB	Output is correct
3	Correct	16 ms	1712 KB	Output is correct
4	Correct	11 ms	1720 KB	Output is correct
5	Correct	13 ms	1684 KB	Output is correct
6	Correct	26 ms	1684 KB	Output is correct
7	Correct	49 ms	1800 KB	Output is correct

Subtask #2

59.00003 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	676 ms	1684 KB	Output is partially correct
2	Partially correct	320 ms	1732 KB	Output is partially correct
3	Partially correct	477 ms	1696 KB	Output is partially correct
4	Partially correct	898 ms	1736 KB	Output is partially correct
5	Partially correct	735 ms	1816 KB	Output is partially correct
6	Partially correct	499 ms	1664 KB	Output is partially correct
7	Partially correct	2256 ms	1748 KB	Output is partially correct
8	Partially correct	3658 ms	2016 KB	Output is partially correct
9	Partially correct	3127 ms	1820 KB	Output is partially correct
10	Partially correct	3197 ms	1936 KB	Output is partially correct
11	Partially correct	3284 ms	1968 KB	Output is partially correct
12	Partially correct	3197 ms	1820 KB	Output is partially correct
13	Partially correct	3152 ms	1876 KB	Output is partially correct
14	Partially correct	3404 ms	1880 KB	Output is partially correct
15	Partially correct	1845 ms	1780 KB	Output is partially correct
16	Partially correct	3470 ms	1788 KB	Output is partially correct
17	Partially correct	845 ms	1796 KB	Output is partially correct
18	Partially correct	895 ms	1760 KB	Output is partially correct
19	Partially correct	906 ms	1860 KB	Output is partially correct
20	Partially correct	928 ms	1808 KB	Output is partially correct
21	Partially correct	839 ms	1876 KB	Output is partially correct
22	Partially correct	986 ms	1780 KB	Output is partially correct
23	Partially correct	1597 ms	1832 KB	Output is partially correct
24	Correct	11 ms	1852 KB	Output is correct
25	Correct	13 ms	1680 KB	Output is correct
26	Correct	13 ms	1808 KB	Output is correct
27	Correct	5 ms	1728 KB	Output is correct
28	Correct	13 ms	1684 KB	Output is correct
29	Correct	30 ms	1960 KB	Output is correct
30	Correct	48 ms	1684 KB	Output is correct