Submission #590925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
590925	2022-07-06T14:40:08 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	45.6666 / 100	4744 ms	1972 KB

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"
               };
int conv(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S6[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}

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 == (conv(i) ^ j))
				ret[i] = true;
	}
	return ret;
}
bitset<6> enc6(int X)
{
	int v = conv(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 >= 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 >= 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;
// 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;
// 	// {
// 	// 	for (v[1] = 0; v[1] < bitsz; v[1]++)
// 	// 	{
// 	// 		for (v[2] = 0; v[2] < bitsz; v[2]++)
// 	// 		{
// 	// 			for (v[3] = 0; v[3] < bitsz; v[3]++)
// 	// 			{
// 	// 				for (v[4] = 0; v[4] < bitsz; v[4]++)
// 	// 				{
// 	// 					for (v[5] = 0; v[5] < bitsz; v[5]++)
// 	// 					{
// 	// 						bool ok = true;
// 	// 						for (int i = 0; i < 6; i++)
// 	// 							for (int j = 0; j < i; j++)
// 	// 								if (v[i] == v[j])
// 	// 									ok = false;
// 	// 						if (ok == false)
// 	// 							continue;
// 	// 						int mx = 0;
// 	// 						for (int i = 0; i < 6; i++)
// 	// 						{
// 	// 							for (int m : ger)
// 	// 							{
// 	// 								int cnt = 0;
// 	// 								int rec = v[i] ^ m;
// 	// 								for (int t = 0; t < 6; t++)
// 	// 									if (gal[v[t]][rec])
// 	// 										cnt++;
// 	// 								mx = max(mx, cnt);
// 	// 							}
// 	// 						}
// 	// 						if (mx < 4)
// 	// 						{
// 	// 							for (int t = 0; t < 6; t++)
// 	// 								cout << bitset<bitcnt>(v[t]) << endl;
// 	// 							cout << endl;
// 	// 							//return 0;
// 	// 						}
// 	// 					}
// 	// 				}
// 	// 			}
// 	// 		}
// 	// 	}
// 	// }
// 	//return 0;
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 6;
// 		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	5 ms	1768 KB	Output is correct
2	Correct	12 ms	1704 KB	Output is correct
3	Correct	14 ms	1800 KB	Output is correct
4	Correct	11 ms	1832 KB	Output is correct
5	Correct	13 ms	1680 KB	Output is correct
6	Correct	24 ms	1788 KB	Output is correct
7	Correct	44 ms	1704 KB	Output is correct

Subtask #2

30.66664 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	814 ms	1756 KB	Output is partially correct
2	Partially correct	362 ms	1704 KB	Output is partially correct
3	Partially correct	409 ms	1664 KB	Output is partially correct
4	Partially correct	1201 ms	1828 KB	Output is partially correct
5	Partially correct	1000 ms	1784 KB	Output is partially correct
6	Partially correct	746 ms	1772 KB	Output is partially correct
7	Partially correct	3062 ms	1748 KB	Output is partially correct
8	Partially correct	4744 ms	1940 KB	Output is partially correct
9	Partially correct	4187 ms	1888 KB	Output is partially correct
10	Partially correct	4212 ms	1800 KB	Output is partially correct
11	Partially correct	4137 ms	1876 KB	Output is partially correct
12	Partially correct	3881 ms	1972 KB	Output is partially correct
13	Partially correct	3944 ms	1888 KB	Output is partially correct
14	Partially correct	3583 ms	1928 KB	Output is partially correct
15	Partially correct	2165 ms	1856 KB	Output is partially correct
16	Partially correct	4589 ms	1880 KB	Output is partially correct
17	Partially correct	1070 ms	1748 KB	Output is partially correct
18	Partially correct	1258 ms	1848 KB	Output is partially correct
19	Partially correct	1170 ms	1812 KB	Output is partially correct
20	Partially correct	1088 ms	1896 KB	Output is partially correct
21	Partially correct	1076 ms	1864 KB	Output is partially correct
22	Partially correct	993 ms	1848 KB	Output is partially correct
23	Partially correct	1819 ms	1804 KB	Output is partially correct
24	Correct	9 ms	1684 KB	Output is correct
25	Correct	11 ms	1688 KB	Output is correct
26	Correct	13 ms	1748 KB	Output is correct
27	Correct	9 ms	1620 KB	Output is correct
28	Correct	13 ms	1684 KB	Output is correct
29	Correct	24 ms	1896 KB	Output is correct
30	Correct	39 ms	1700 KB	Output is correct