oj.uz

답안 #591485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591485 2022-07-07T13:42:53 Z tutis Flight to the Ford (BOI22_communication) C++17
70 / 100
 4650 ms 2804 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"
               };
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 = 11;
bitset < 1 << bitcnt > decB(int x) //4 bit x
{
	vector<int>ger;
	for (int m = 0; m < (1 << bitcnt); 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 < 1 << bitcnt > ret;
	for (int j : ger)
		ret[x ^ j] = true;
	return ret;
}
bitset < 1 << bitcnt > encB(int v)
{
	int val = 0;
	int vv = v;
	for (int t = 0; t < bitcnt; t++)
	{
		val += (send(v % 2) << t);
		v /= 2;
	}
	auto ret = decB(val);
	assert(ret[vv] == true);
	return ret;
}
void encode(int N, int X)
{
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	if (N >= (1 << bitcnt))
	{
		int v = N / (1 << bitcnt);
		int vv = (X - 1) / v;
		vv = min(vv, (1 << bitcnt) - 1);
		bitset < (1 << bitcnt) > gal = encB(vv);
		int sz[(1 << bitcnt)];
		for (int i = 0; i < (1 << bitcnt); i++)
			sz[i] = v;
		sz[(1 << bitcnt) - 1] = N - v * ((1 << bitcnt) - 1);
		int s = 0;
		for (int i = 0; i < (1 << bitcnt); i++)
		{
			if (gal[i])
				s += sz[i];
			else if (i < vv)
				X -= sz[i];
		}
		encode(s, 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;
	}
}
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;
	}
	if (N >= (1 << bitcnt))
	{
		int re = 0;
		for (int t = 0; t < bitcnt; t++)
			re += receive() << t;
		bitset < (1 << bitcnt) > gal = decB(re);
		int v = N / (1 << bitcnt);
		int sz[(1 << bitcnt)];
		for (int i = 0; i < (1 << bitcnt); i++)
			sz[i] = v;
		sz[(1 << bitcnt) - 1] = N - v * ((1 << bitcnt) - 1);
		int s = 0;
		for (int i = 0; i < (1 << bitcnt); 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 < (1 << bitcnt); 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;
	}
	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;
	}
	return { -1, -1};
}
// int main()
// {
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 1000;
// 		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 7 ms 1796 KB Output is correct
2 Correct 13 ms 1780 KB Output is correct
3 Correct 12 ms 1776 KB Output is correct
4 Correct 13 ms 1744 KB Output is correct
5 Correct 16 ms 1672 KB Output is correct
6 Correct 27 ms 1936 KB Output is correct
7 Correct 49 ms 1832 KB Output is correct

Subtask #2
55.000015 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 755 ms 1948 KB Output is partially correct
2 Partially correct 495 ms 1964 KB Output is partially correct
3 Partially correct 488 ms 2052 KB Output is partially correct
4 Partially correct 1081 ms 1820 KB Output is partially correct
5 Partially correct 1041 ms 1964 KB Output is partially correct
6 Partially correct 793 ms 1988 KB Output is partially correct
7 Partially correct 2723 ms 2192 KB Output is partially correct
8 Partially correct 4650 ms 2804 KB Output is partially correct
9 Partially correct 3956 ms 2680 KB Output is partially correct
10 Partially correct 3966 ms 2416 KB Output is partially correct
11 Partially correct 3694 ms 2504 KB Output is partially correct
12 Partially correct 4010 ms 2404 KB Output is partially correct
13 Partially correct 3571 ms 2380 KB Output is partially correct
14 Partially correct 3886 ms 2400 KB Output is partially correct
15 Partially correct 2154 ms 2332 KB Output is partially correct
16 Partially correct 4120 ms 2116 KB Output is partially correct
17 Partially correct 1162 ms 2184 KB Output is partially correct
18 Partially correct 1097 ms 2168 KB Output is partially correct
19 Partially correct 1118 ms 2140 KB Output is partially correct
20 Partially correct 1115 ms 1880 KB Output is partially correct
21 Partially correct 1153 ms 2088 KB Output is partially correct
22 Partially correct 1053 ms 2248 KB Output is partially correct
23 Partially correct 1704 ms 2180 KB Output is partially correct
24 Correct 11 ms 1620 KB Output is correct
25 Correct 13 ms 1876 KB Output is correct
26 Correct 19 ms 1720 KB Output is correct
27 Correct 11 ms 1720 KB Output is correct
28 Correct 8 ms 1704 KB Output is correct
29 Correct 29 ms 1868 KB Output is correct
30 Correct 50 ms 1668 KB Output is correct