Submission #546345

#	Time	Username	Problem	Language	Result	Execution time	Memory
546345		jjang36524	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	74 ms	8468 KiB

Anna

#include "Anna.h"
#include "Bruno.h"
#include <vector>
#include <algorithm>
using namespace std;
#define F1 63
#define F2 44
vector<int> a;
long long fib[65];
void Anna(int N, std::vector<char> S) 
{
	int i;
	fib[0] = 1;
	fib[1]=2;
	for (i = 2; i <= F1; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	int xh = 0;
	for (i = 0; i < N; i++)
	{
		if (!xh && S[i] == 'X')
		{
			xh = 1;
			a.push_back(1);
			a.push_back(0);
		}
		else if (xh)
		{
			a.push_back((S[i] == 'Z' && (i + 1 == N || S[i + 1] != 'Z')));
		}
		else
			a.push_back(0);
	}
	for (; a.size() % F1;)
	{
		a.push_back(0);
	}
	for (i = 0; i < a.size(); i += F1)
	{
		int j;
		long long ans = 0;
		for (j = i + F1 - 1; j >= i; j--)
		{
			if (a[j] == 1)
			{
				ans += fib[(i + F1 - 1) - j];
			}
		}
		for (j = 0; j < F2; j++)
		{
			Send((ans >> j) & 1);
		}
	}
}

Bruno

#include "Anna.h"
#include "Bruno.h"
#include <vector>
#include <algorithm>
using namespace std;
#define F1 63
#define F2 44
vector<int> a;
long long fib[65];
void Bruno(int N, int L, std::vector<int> A) 
{
	int i;
	fib[0] = 1;
	fib[1] = 2;
	for (i = 2; i <= F1; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	vector<int>t;
	for (i = 0; i < L; i+=F2)
	{
		long long cu = 0;
		int j;
		for (j = i; j < i+F2; j++)
		{
			cu += (long long)A[j] << ((long long)(j - i));
		}
		for (j = F1 - 1; j >= 0; j--)
		{
			if (fib[j] <= cu)
			{
				cu -= fib[j];
				t.push_back(1);
			}
			else
			{
				t.push_back(0);
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		if (t[i] == 1)
		{
			break;
		}
		Remove(i);
	}
	int finalrm = i;
	i+=2;
	int la = i-1;
	for (; i < N+1; i++)
	{
		if (t[i])
		{
			int j;
			for (j = i - 1; j > la; j--)
				Remove(j-1);
			Remove(i-1);
			la = i;
		}
	}
	i = min(i, N + 1);
	int j;
	for (j = i - 1; j > la; j--)
		Remove(j - 1);
	if (finalrm < N)
		Remove(finalrm);
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:39:16: 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 < a.size(); i += F1)
      |              ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95