Submission #590887

#	Time	Username	Problem	Language	Result	Execution time	Memory
590887		tutis	Flight to the Ford (BOI22_communication)	C++17	30 / 100	6190 ms	2036 KiB

communication

#include <bits/stdc++.h>
using namespace std;
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);
}
void encode(int N, int X)
{
	if (N < 3)
		return;
	if (N == 3)
	{
		enc3(X);
		return;
	}
	int v = N / 3;
	int vv = 3;
	if (X <= v)
		vv = 1;
	else if (X <= 2 * v)
		vv = 2;
	int val = enc3(vv);
	assert(val != vv);
	if (val == 2)
	{
		if (vv == 1)
			encode(N - v, X);
		if (vv == 3)
			encode(N - v, X - v);
	}
	if (val == 1)
		encode(N - v, X - v);
	if (val == 3)
		encode(2 * v, X);
}
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;
	}
	else {
		int re = 0;
		for (int t = 0; t < 4; t++)
			re += receive() << t;
		int val = dec3(re);
		int v = N / 3;
		if (val == 2)
		{
			pair<int, int>r = decode(N - v);
			if (r.first > v)
				r.first += v;
			if (r.second > v)
				r.second += v;
			return r;
		}
		if (val == 1)
		{
			pair<int, int>r = decode(N - v);
			r.first += v;
			r.second += v;
			return r;
		}
		if (val == 3)
			return decode(2 * v);
	}
}
// int main()
// {
// 	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 a = 0;
// 	{
// 		for (int b = 0; b < 16; b++)
// 		{
// 			for (int c = 0; c < 16; c++)
// 			{
// 				if (a == b || b == c || c == a)
// 					continue;
// 				set<int>A;
// 				set<int>B;
// 				set<int>C;
// 				for (int i : ger)
// 				{
// 					A.insert(i ^ a);
// 					B.insert(i ^ b);
// 					C.insert(i ^ c);
// 				}
// 				bool ok = true;
// 				for (int i : ger)
// 				{
// 					int v1 = i ^ b;
// 					int v2 = i ^ c;
// 					if (A.count(v1) > 0 && A.count(v2) > 0)
// 					{
// 						ok = false;
// 						break;
// 					}
// 				}
// 				for (int i : ger)
// 				{
// 					int v1 = i ^ a;
// 					int v2 = i ^ c;
// 					if (B.count(v1) > 0 && B.count(v2) > 0)
// 					{
// 						ok = false;
// 						break;
// 					}
// 				}
// 				for (int i : ger)
// 				{
// 					int v1 = i ^ a;
// 					int v2 = i ^ b;
// 					if (C.count(v1) > 0 && C.count(v2) > 0)
// 					{
// 						ok = false;
// 						break;
// 					}
// 				}
// 				if (ok)
// 				{
// 					// cout << bitset<4>(a) << endl;
// 					// cout << bitset<4>(b) << endl;
// 					// cout << bitset<4>(c) << endl;
// 					// cout << endl;
// 				}
// 			}
// 		}
// 	}
// 	for (int t = 0; t < 1000; t++)
// 	{
// 		int N = 4;
// 		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);
// 	}
// }

Compilation message (stderr)

communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

• Subtask 1: 15 / 15
• Subtask 2: 15.000034999999999 / 85