답안 #591707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591707	2022-07-07T18:56:33 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	88 / 100	3235 ms	2048 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 = 29;
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))
		{
			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))
		{
			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	11 ms	1844 KB	Output is correct
2	Correct	13 ms	1760 KB	Output is correct
3	Correct	16 ms	1732 KB	Output is correct
4	Correct	12 ms	1736 KB	Output is correct
5	Correct	14 ms	1716 KB	Output is correct
6	Correct	30 ms	2048 KB	Output is correct
7	Correct	32 ms	1704 KB	Output is correct

Subtask #2

73.00004 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	659 ms	1672 KB	Output is partially correct
2	Partially correct	379 ms	1676 KB	Output is partially correct
3	Partially correct	354 ms	1776 KB	Output is partially correct
4	Partially correct	613 ms	1732 KB	Output is partially correct
5	Partially correct	692 ms	1728 KB	Output is partially correct
6	Partially correct	696 ms	1760 KB	Output is partially correct
7	Partially correct	2223 ms	1812 KB	Output is partially correct
8	Partially correct	3036 ms	2024 KB	Output is partially correct
9	Partially correct	2649 ms	1868 KB	Output is partially correct
10	Partially correct	2689 ms	1948 KB	Output is partially correct
11	Partially correct	2520 ms	1968 KB	Output is partially correct
12	Partially correct	2579 ms	1996 KB	Output is partially correct
13	Partially correct	2784 ms	1856 KB	Output is partially correct
14	Partially correct	2772 ms	1896 KB	Output is partially correct
15	Partially correct	1453 ms	1800 KB	Output is partially correct
16	Partially correct	3235 ms	1768 KB	Output is partially correct
17	Partially correct	518 ms	1856 KB	Output is partially correct
18	Partially correct	634 ms	1808 KB	Output is partially correct
19	Partially correct	828 ms	1868 KB	Output is partially correct
20	Partially correct	880 ms	1728 KB	Output is partially correct
21	Partially correct	690 ms	1788 KB	Output is partially correct
22	Partially correct	775 ms	1812 KB	Output is partially correct
23	Partially correct	1314 ms	1752 KB	Output is partially correct
24	Correct	5 ms	1696 KB	Output is correct
25	Correct	13 ms	1692 KB	Output is correct
26	Correct	14 ms	1708 KB	Output is correct
27	Correct	7 ms	1672 KB	Output is correct
28	Correct	12 ms	1732 KB	Output is correct
29	Correct	21 ms	1912 KB	Output is correct
30	Correct	38 ms	1800 KB	Output is correct