oj.uz

답안 #590968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590968 2022-07-06T16:10:15 Z tutis Flight to the Ford (BOI22_communication) C++17
74 / 100
 3658 ms 2016 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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