답안 #590940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590940	2022-07-06T15:11:01 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	57 / 100	3772 ms	2056 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"
               };
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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1744 KB	Output is correct
2	Correct	10 ms	1740 KB	Output is correct
3	Correct	12 ms	1700 KB	Output is correct
4	Correct	13 ms	1752 KB	Output is correct
5	Correct	16 ms	1784 KB	Output is correct
6	Correct	28 ms	1768 KB	Output is correct
7	Correct	53 ms	1740 KB	Output is correct

Subtask #2

42.00003 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	810 ms	1700 KB	Output is partially correct
2	Partially correct	471 ms	1664 KB	Output is partially correct
3	Partially correct	527 ms	1720 KB	Output is partially correct
4	Partially correct	853 ms	1664 KB	Output is partially correct
5	Partially correct	687 ms	1724 KB	Output is partially correct
6	Partially correct	733 ms	1700 KB	Output is partially correct
7	Partially correct	2290 ms	1804 KB	Output is partially correct
8	Partially correct	3713 ms	2056 KB	Output is partially correct
9	Partially correct	3270 ms	1880 KB	Output is partially correct
10	Partially correct	3252 ms	1932 KB	Output is partially correct
11	Partially correct	3443 ms	1800 KB	Output is partially correct
12	Partially correct	3378 ms	1804 KB	Output is partially correct
13	Partially correct	3383 ms	1792 KB	Output is partially correct
14	Partially correct	3239 ms	1924 KB	Output is partially correct
15	Partially correct	1726 ms	1804 KB	Output is partially correct
16	Partially correct	3772 ms	1824 KB	Output is partially correct
17	Partially correct	1039 ms	1732 KB	Output is partially correct
18	Partially correct	1033 ms	1868 KB	Output is partially correct
19	Partially correct	1083 ms	1740 KB	Output is partially correct
20	Partially correct	889 ms	1844 KB	Output is partially correct
21	Partially correct	926 ms	1728 KB	Output is partially correct
22	Partially correct	1022 ms	1832 KB	Output is partially correct
23	Partially correct	1477 ms	1780 KB	Output is partially correct
24	Correct	10 ms	1692 KB	Output is correct
25	Correct	10 ms	1804 KB	Output is correct
26	Correct	17 ms	1684 KB	Output is correct
27	Correct	9 ms	1692 KB	Output is correct
28	Correct	10 ms	1720 KB	Output is correct
29	Correct	23 ms	1772 KB	Output is correct
30	Correct	38 ms	1700 KB	Output is correct