답안 #591704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591704	2022-07-07T18:51:28 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	88 / 100	3134 ms	2108 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)
	{
		while (N % 4 != 0)
			N++;
		int v = N / 4;
		int vv = (X - 1) / v;
		vv = min(vv, 3);
		bitset<4>gal = enc4(vv);
		int s = 0;
		for (int i = 0; i < 4; i++)
		{
			if (gal[i])
			{
				s += v;
			}
			else if (i < vv)
				X -= v;
		}
		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 N1 = N;
		while (N % 4 != 0)
			N++;
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		bitset<4> gal = dec4(re);
		int v = N / 4;
		int s = 0;
		for (int i = 0; i < 4; i++)
			if (gal[i])
				s += v;
		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 + v && ger1 == false)
				{
					for (int j = 0; j < i; j++)
						if (gal[j] == false)
							r.first += v;
					ger1 = true;
				}
				if (r.second > sum && r.second <= sum + v && ger2 == false)
				{
					for (int j = 0; j < i; j++)
						if (gal[j] == false)
							r.second += v;
					ger2 = true;
				}
				sum += v;
			}
		}
		r.first = min(r.first, N1);
		r.second = min(r.second, N1);
		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	1708 KB	Output is correct
2	Correct	12 ms	1804 KB	Output is correct
3	Correct	18 ms	1708 KB	Output is correct
4	Correct	13 ms	1808 KB	Output is correct
5	Correct	7 ms	1688 KB	Output is correct
6	Correct	21 ms	1800 KB	Output is correct
7	Correct	59 ms	1668 KB	Output is correct

Subtask #2

73.00004 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	875 ms	1724 KB	Output is partially correct
2	Partially correct	461 ms	1724 KB	Output is partially correct
3	Partially correct	561 ms	1744 KB	Output is partially correct
4	Partially correct	900 ms	1712 KB	Output is partially correct
5	Partially correct	663 ms	1696 KB	Output is partially correct
6	Partially correct	400 ms	1752 KB	Output is partially correct
7	Partially correct	1993 ms	1768 KB	Output is partially correct
8	Partially correct	3134 ms	2108 KB	Output is partially correct
9	Partially correct	2752 ms	1868 KB	Output is partially correct
10	Partially correct	2622 ms	1812 KB	Output is partially correct
11	Partially correct	2768 ms	1796 KB	Output is partially correct
12	Partially correct	2776 ms	1796 KB	Output is partially correct
13	Partially correct	2750 ms	1876 KB	Output is partially correct
14	Partially correct	2784 ms	1968 KB	Output is partially correct
15	Partially correct	1358 ms	1848 KB	Output is partially correct
16	Partially correct	3125 ms	1760 KB	Output is partially correct
17	Partially correct	816 ms	1740 KB	Output is partially correct
18	Partially correct	748 ms	1744 KB	Output is partially correct
19	Partially correct	744 ms	1804 KB	Output is partially correct
20	Partially correct	859 ms	1868 KB	Output is partially correct
21	Partially correct	769 ms	1744 KB	Output is partially correct
22	Partially correct	797 ms	1796 KB	Output is partially correct
23	Partially correct	1279 ms	1876 KB	Output is partially correct
24	Correct	8 ms	1740 KB	Output is correct
25	Correct	11 ms	1704 KB	Output is correct
26	Correct	15 ms	1700 KB	Output is correct
27	Correct	9 ms	1756 KB	Output is correct
28	Correct	13 ms	1800 KB	Output is correct
29	Correct	24 ms	1904 KB	Output is correct
30	Correct	48 ms	1620 KB	Output is correct