답안 #591714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591714	2022-07-07T19:19:18 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	88 / 100	3296 ms	2088 KB

communication

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#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"
               };
int conv4(int i)
{
	int v = 0;
	int p = 1;
	for (char c : S4[i])
	{
		if (c == '1')
			v += p;
		p *= 2;
	}
	return v;
}
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;
}
const int bitcnt = 30;
int bitcnt1 = 14;
int encB(int v)
{
	int val = 0;
	for (int t = 0; t < bitcnt1; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	return val;
}
int C[40][2];
bool prec = false;
int getL(int l)
{
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	return C[l][0] + C[l][1];
}
int cntT(int m, int l, int g, int x = 0)
{
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	if (m == (1 << l))
	{
		return C[l][0] + C[l][1];
	}
	int ret = 0;
	for (int b = l; b >= 1; b--)
	{
		int vv = m & (1 << (b - 1));
		int gg = g & (1 << (b - 1));
		m -= vv;
		g -= gg;
		vv /= (1 << (b - 1));
		gg /= (1 << (b - 1));
		int f1 = -1;
		for (int nxt : {0, 1}) {
			int f = gg ^ nxt;
			if (f == 1 && x == 1)
				continue;
			if (nxt < vv)
				ret += C[b][f];
			else if (nxt == vv)
				f1 = f;
		}
		if (f1 == -1)
			break;
		x = f1;
	}
	return ret;
}
int kth(int k, int l, int g, int x = 0)
{
	if (l == 0)
		return 0;
	if (prec == false)
	{
		C[0][0] = 1;
		for (int i = 1; i < 40; i++)
		{
			C[i][0] = C[i - 1][0] + C[i - 1][1];
			C[i][1] = C[i - 1][0];
		}
		prec = true;
	}
	int s = 0;
	for (int b = l; b >= 1; b--)
	{
		int gg = g & (1 << (b - 1));
		g -= gg;
		gg /= (1 << (b - 1));
		for (int nxt : {0, 1})
		{
			int f = gg ^ nxt;
			if (f == 1 && x == 1)
				continue;
			if (k < C[b][f])
			{
				s += ((1 << (b - 1)) * nxt);
				x = f;
				break;
			}
			else
				k -= C[b][f];
		}
	}
	return s;
}
void encode(int N, int X)
{
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	for (int bc = bitcnt; bc >= 5; bc--)
		if (N >= (1 << bc) * 0.97)
		{
			N = max(N, 1 << bc);
			int v = N / (1 << bc);
			int k1 = N % (1 << bc);
			int k0 = (1 << bc) - k1;
			assert(k0 * v + k1 * (v + 1) == N);
			int vv = (X - 1) / v;
			if (vv >= k0)
				vv = k0 + (X - k0 * v - 1) / (v + 1);
			assert(X >= 1 && X <= N);
			assert(vv >= 0 && vv < (1 << bc));

			bitcnt1 = bc;
			int gal1 = encB(vv);
			int c1 = getL(bc);
			int kk0 = cntT(k0, bc, gal1);
			int s = (v + 1) * c1 - kk0;
			int c = cntT(vv, bc, gal1);
			if (X <= k0 * v + v + 1)
			{
				X -= (vv - c) * v;
			}
			else
			{
				X -= vv * (v + 1) - k0;
				X += c * (v + 1) - kk0;
			}
			encode(s, X);
			return;
		}
	if (N >= 4)
	{
		int sz[4];
		for (int i = 0; i < 4; i++)
			sz[i] = N / 4;
		for (int i = 0; i < (N % 4); i++)
			sz[i]++;
		int vv = 0;
		{
			int XX = X;
			while (XX > sz[vv])
			{
				XX -= sz[vv];
				vv++;
			}
		}
		bitset<4>gal = enc4(vv);
		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;
	}
}
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;
	}
	for (int bc = bitcnt; bc >= 5; bc--)
		if (N >= (1 << bc) * 0.97)
		{
			N = max(N, 1 << bc);
			int re = 0;
			for (int t = 0; t < bc; t++)
				re += receive() << t;
			int v = N / (1 << bc);
			int k1 = N % (1 << bc);
			int k0 = (1 << bc) - k1;

			int c1 = getL(bc);
			int kk0 = cntT(k0, bc, re);
			int s = (v + 1) * c1 - kk0;

			pair<int, int>r = decode(s);

			auto blo = [&](int p)->int
			{
				int i = (p - 1) / v;
				if (i >= kk0)
					i = kk0 + (p - kk0 * v - 1) / (v + 1);
				return i;
			};
			int i1 = kth(blo(r.first), bc, re);
			int i2 = kth(blo(r.second), bc, re);
			if (i1 <= k0)
				r.first += v * (i1 - cntT(i1, bc, re));
			else
			{
				r.first += (k0 - kk0) * v;
				r.first += (v + 1) * (i1 - cntT(i1, bc, re) - (k0 - kk0));
			}
			if (i2 <= k0)
				r.second += v * (i2 - cntT(i2, bc, re));
			else
			{
				r.second += (k0 - kk0) * v;
				r.second += (v + 1) * (i2 - cntT(i2, bc, re) - (k0 - kk0));
			}
			return r;
		}
	if (N >= 4)
	{
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		bitset<4> gal = dec4(re);
		int sz[4];
		for (int i = 0; i < 4; i++)
			sz[i] = N / 4;
		for (int i = 0; i < (N % 4); i++)
			sz[i]++;
		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;
	}
	return { -1, -1};
}
// int main()
// {
// 	mt19937 rng(0);
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 189189;
// 		int val = (rng() % 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	8 ms	1724 KB	Output is correct
2	Correct	12 ms	1760 KB	Output is correct
3	Correct	15 ms	1716 KB	Output is correct
4	Correct	13 ms	1704 KB	Output is correct
5	Correct	13 ms	1740 KB	Output is correct
6	Correct	21 ms	1848 KB	Output is correct
7	Correct	46 ms	1764 KB	Output is correct

Subtask #2

73.00004 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	859 ms	1972 KB	Output is partially correct
2	Partially correct	329 ms	1748 KB	Output is partially correct
3	Partially correct	418 ms	1660 KB	Output is partially correct
4	Partially correct	741 ms	1824 KB	Output is partially correct
5	Partially correct	618 ms	1892 KB	Output is partially correct
6	Partially correct	637 ms	1740 KB	Output is partially correct
7	Partially correct	1888 ms	1780 KB	Output is partially correct
8	Partially correct	3296 ms	2088 KB	Output is partially correct
9	Partially correct	2953 ms	2028 KB	Output is partially correct
10	Partially correct	2849 ms	1816 KB	Output is partially correct
11	Partially correct	2882 ms	1880 KB	Output is partially correct
12	Partially correct	2569 ms	2076 KB	Output is partially correct
13	Partially correct	2761 ms	1880 KB	Output is partially correct
14	Partially correct	2693 ms	1896 KB	Output is partially correct
15	Partially correct	1613 ms	1820 KB	Output is partially correct
16	Partially correct	3286 ms	1872 KB	Output is partially correct
17	Partially correct	703 ms	1764 KB	Output is partially correct
18	Partially correct	843 ms	1784 KB	Output is partially correct
19	Partially correct	756 ms	1732 KB	Output is partially correct
20	Partially correct	883 ms	1728 KB	Output is partially correct
21	Partially correct	781 ms	1816 KB	Output is partially correct
22	Partially correct	808 ms	1724 KB	Output is partially correct
23	Partially correct	1325 ms	1828 KB	Output is partially correct
24	Correct	12 ms	1868 KB	Output is correct
25	Correct	13 ms	1884 KB	Output is correct
26	Correct	12 ms	1696 KB	Output is correct
27	Correct	11 ms	1688 KB	Output is correct
28	Correct	19 ms	1792 KB	Output is correct
29	Correct	29 ms	1804 KB	Output is correct
30	Correct	23 ms	1740 KB	Output is correct