Submission #601791

#	Time	Username	Problem	Language	Result	Execution time	Memory
601791		jjang36524	Flight to the Ford (BOI22_communication)	C++17	0 / 100	412 ms	200 KiB

communication

#include"communication.h"
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
#include <bits/stdc++.h>
using namespace std;
void encode(int N, int X)
{
	int lim = 1000000002;
	while (lim > 5)
	{
		int dp[40];
		int i;
		vector<int>x;
		for (i = 0;; i++)
		{
			if ((1 << i) >= lim)
				break;
			x.push_back(send((X >> i) & 1));
		}
		int v = i;
		dp[0] = 1;
		dp[1] = 2;
		for (i = 2; i <= v; i++)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		int nlim = 0;
		int nx = 0;
		for (i = 0; i < x.size(); i++)
		{
			if (i != x.size() && x[i] != ((X >> i) & 1))
			{
				nx += dp[i];
			}
		}
		nlim = dp[v];
		X = nx;
		lim = nlim;
	}
	long long v = 125;
	int arr[5][10];
	int i;
	for (i = 0; i < 5; i++)
	{
		int j;
		for (j = 0; j < 10; j++)
		{
			v *= 1272;
			v += 125792;
			v %= 12592043;
			arr[i][j] = !(v & (1 << 16));
		}
	}
	for (i = 0; i < 10; i++)
	{
		send(arr[X][i]);
	}
}

std::pair<int, int> decode(int N)
{
	srand(1);
	long long v = 125;
	int arr[33][50];
	int i;
	for (i = 0; i < 5; i++)
	{
		int j;
		for (j = 0; j < 10; j++)
		{
			v *= 1272;
			v += 125792;
			v %= 12592043;
			arr[i][j] = !(v & (1 << 16));
		}
	}
	int lim = 1000000002;
	vector<int>lims;
	vector<int>vs;
	while (lim > 5)
	{
		lims.push_back(lim);
		int dp[40];
		dp[0] = 1;
		dp[1] = 2;
		int i;
		for (i = 0;; i++)
		{
			if ((1 << i) >= lim)
				break;
		}
		int v = i;
		vs.push_back(v);
		for (i = 2; i <= v; i++)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		lim = dp[v];

	}
	vector<int>r;
	for (i = 0; i < 124; i++)
	{
		r.push_back(receive());
	}
	vector<int>st;
	for (i = 0; i < 5; i++)
	{
		int bef = 0;
		int j;
		for (j = 0; j < 10; j++)
		{
			if (bef && (r[j + 114] != arr[i][j]))
				break;
			bef = r[j + 114] != arr[i][j];
		}
		if (j == 10)
			st.push_back(i);
	}
	pair<int, int>ans = { 1,1 };
	for (i = 0; i < st.size(); i++)
	{
		vector<int>nvs = vs;
		vector<int>nr = r;
		int cur = 114;
		int nv = st[i];
		while (cur)
		{
			int bc = cur - 1;
			cur -= vs.back();
			vs.pop_back();
			int j;
			int dp[40];
			dp[0] = 1;
			dp[1] = 2;
			int nnv = 0;
			int i;
			for (i = 2; i <= 39; i++)
			{
				dp[i] = dp[i - 1] + dp[i - 2];
			}
			for (j = bc; j >= cur; j--)
			{
				if (nv >= dp[j - cur])
				{
					r[j] ^= 1;
					nv -= dp[j - cur];
				}
			}
			for (j = cur; j <= bc; j++)
			{
				nnv += r[j] << (j - cur);
			}
			nv = nnv;
		}
		vs = nvs;
		r = nr;
		if (i == 0)
			ans.first = nv;
		else
			ans.second = nv;
	}
	ans.first = min(ans.first, N);
	ans.second = min(ans.second, N);
	ans.first = max(ans.first, 1);
	ans.second = max(ans.second, 1);
	return ans;
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (i = 0; i < x.size(); i++)
      |               ~~^~~~~~~~~~
communication.cpp:41:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    if (i != x.size() && x[i] != ((X >> i) & 1))
      |        ~~^~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for (i = 0; i < st.size(); i++)
      |              ~~^~~~~~~~~~~

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