답안 #672529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672529	2022-12-16T14:08:11 Z	LittleCube	Flight to the Ford (BOI22_communication)	C++17	15 / 100	697 ms	1856 KB

communication

#include "communication.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct state
{
	int szA = 0, szB = 0;
	vector<pii> A, B;
};

// 11 -> 10 01 11
// 10 -> 10 00 11
// 00 -> 00 01

void split(state &s, state &L, state &R)
{
	auto &[szA, szB, A, B] = s;
	int lA = szA / 2, lB = szB / 2;
	for (auto [l, r] : A)
	{
		if (r - l + 1 <= lA)
			L.A.emplace_back(pii(l, r));
		else if (lA <= 0)
			R.A.emplace_back(pii(l, r));
		else
		{
			L.A.emplace_back(pii(l, l + lA - 1));
			R.A.emplace_back(pii(l + lA, r));
		}
		lA -= r - l + 1;
	}
	R.B = L.A;
	L.B = R.A;
	for (auto [l, r] : B)
	{
		if (r - l + 1 <= lB)
			L.A.emplace_back(pii(l, r));
		else if (lB <= 0)
			R.A.emplace_back(pii(l, r));
		else
		{
			L.A.emplace_back(pii(l, l + lB - 1));
			R.A.emplace_back(pii(l + lB, r));
		}
		lB -= r - l + 1;
	}
}

pii divide(state s, int x, bool encode)
{
	auto &[szA, szB, A, B] = s;
	for(auto [l, r] : A)
		szA += r - l + 1;
	for(auto [l, r] : B)
		szB += r - l + 1;
	// cerr << "divide " << szA << " A ";
	// for(auto [i, j] : A)
	// 	cerr << "[" << i << ", " << j << "] ";
	// cerr << szB << " B ";
	// for(auto [i, j] : B)
	// 	cerr << "[" << i << ", " << j << "] ";
	// cerr << '\n';
	if (szA <= 2 && szA + szB <= 3)
	{
		vector<int> v;
		for (auto [l, r] : A)
			for (int i = l; i <= r; i++)
				v.emplace_back(i);
		for (auto [l, r] : B)
			for (int i = l; i <= r; i++)
				v.emplace_back(i);
		if (encode)
		{

			if (x == v[0])
				send(1), send(1);
			else if (x == v[1])
				send(1), send(0);
			else
				send(0), send(0);
			return pii(0, 0);
		}
		else
		{
			int res = receive() * 2;
			res += receive();
			if (res == 2 || res == 3)
				return pii(v[0], v[1]);
			else if (res == 1)
				return pii(v[0], v[2]);
			else
				return pii(v[1], v[2]);
		}
	}
	state L, R;
	split(s, L, R);
	int signal = 1;
	for (auto [l, r] : L.A)
		if (l <= x && x <= r)
			signal = 0;
	int res;
	if(encode)
		res = send(signal);
	else
		res = receive();

	if (res == 0)
		return divide(L, x, encode);
	else
		return divide(R, x, encode);
}

void encode(int N, int X)
{
	state s;
	s.A.emplace_back(pii(1, N));
	divide(s, X, 1);
}

pii decode(int N)
{
	state s;
	s.A.emplace_back(pii(1, N));
	return divide(s, 0, 0);
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	1764 KB	Output is correct
2	Correct	15 ms	1684 KB	Output is correct
3	Correct	12 ms	1716 KB	Output is correct
4	Correct	11 ms	1660 KB	Output is correct
5	Correct	13 ms	1724 KB	Output is correct
6	Correct	26 ms	1844 KB	Output is correct
7	Correct	55 ms	1764 KB	Output is correct

Subtask #2

0.0 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	697 ms	1856 KB	Output is partially correct
2	Incorrect	3 ms	380 KB	Not correct
3	Halted	0 ms	0 KB	-