답안 #591709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591709	2022-07-07T19:04:00 Z	tutis	Flight to the Ford (BOI22_communication)	C++17	84 / 100	3307 ms	1968 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 mincnt = 7;
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)
{
	//cout << N << " " << kiekis << endl;
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	for (int bc = bitcnt; bc >= mincnt; 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 >= mincnt; 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 < 10; t++)
// 	{
// 		kiekis = 0;
// 		int N = 1e9;
// 		int val = (rng() % N) + 1;
// 		encode(N, val);
// 		pair<int, int>v = decode(N);
// 		assert(v.first == val || v.second == val);
// 	}
// }

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	1792 KB	Output is correct
2	Correct	14 ms	1748 KB	Output is correct
3	Correct	14 ms	1780 KB	Output is correct
4	Correct	12 ms	1640 KB	Output is correct
5	Correct	10 ms	1736 KB	Output is correct
6	Correct	24 ms	1812 KB	Output is correct
7	Correct	42 ms	1760 KB	Output is correct

Subtask #2

69.000025 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	712 ms	1664 KB	Output is partially correct
2	Partially correct	370 ms	1664 KB	Output is partially correct
3	Partially correct	359 ms	1688 KB	Output is partially correct
4	Partially correct	826 ms	1708 KB	Output is partially correct
5	Partially correct	683 ms	1664 KB	Output is partially correct
6	Partially correct	635 ms	1704 KB	Output is partially correct
7	Partially correct	1980 ms	1836 KB	Output is partially correct
8	Partially correct	3002 ms	1968 KB	Output is partially correct
9	Partially correct	2610 ms	1940 KB	Output is partially correct
10	Partially correct	2996 ms	1880 KB	Output is partially correct
11	Partially correct	3307 ms	1844 KB	Output is partially correct
12	Partially correct	2475 ms	1848 KB	Output is partially correct
13	Partially correct	3007 ms	1912 KB	Output is partially correct
14	Partially correct	2544 ms	1784 KB	Output is partially correct
15	Partially correct	1475 ms	1796 KB	Output is partially correct
16	Partially correct	3210 ms	1760 KB	Output is partially correct
17	Partially correct	721 ms	1740 KB	Output is partially correct
18	Partially correct	782 ms	1736 KB	Output is partially correct
19	Partially correct	752 ms	1820 KB	Output is partially correct
20	Partially correct	768 ms	1752 KB	Output is partially correct
21	Partially correct	919 ms	1840 KB	Output is partially correct
22	Partially correct	880 ms	1820 KB	Output is partially correct
23	Partially correct	1500 ms	1724 KB	Output is partially correct
24	Correct	8 ms	1816 KB	Output is correct
25	Correct	10 ms	1744 KB	Output is correct
26	Correct	25 ms	1656 KB	Output is correct
27	Correct	9 ms	1880 KB	Output is correct
28	Correct	17 ms	1720 KB	Output is correct
29	Correct	24 ms	1784 KB	Output is correct
30	Correct	36 ms	1736 KB	Output is correct