Submission #664725

#	Time	Username	Problem	Language	Result	Execution time	Memory
664725		blue	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	210 ms	8688 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
 
namespace
{
	using namespace std;
	
	using vi = vector<int>;
	using pii = pair<int, int>;
	using vpii = vector<pii>;
	using ll = long long;
	using vll = vector<ll>;
	#define sz(x) int(x.size())
 
	const int obs = 76;
	const int cbs = 53;
 
	vi encode(vi A)
	{
		while(sz(A) % obs != 0)
			A.push_back(0);
 
		// cerr << "to encode: ";
		// for(int u = 0; u < sz(A); u++)
		// 	cerr << A[u];
		// cerr << '\n';
 
 
		ll pow2[cbs];
		pow2[0] = 1;
		for(int i = 1; i < cbs; i++)
			pow2[i] = pow2[i-1] * 2LL;
 
 
		ll dp[1 + obs][2];
 
		dp[1][0] = 1;
		dp[1][1] = 1;
 
		for(int i = 2; i <= obs; i++)
		{
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0];
		}
 
 
		// cerr << "dp values: \n";
		// for(int i = 1; i <= obs; i++)
		// 	cerr << dp[i][0] << ' ' << dp[i][1] << '\n';
 
		vi res;
 
 
		for(int i = 0; i < sz(A); i += obs)
		{
			// cerr << "i = " << i << '\n';
			vi a;
			ll val = 0;
			for(int j = i; j < i + obs; j++)
			{
				a.push_back(A[j]);
			}
 
 
			for(int j = 0; j < obs; j++)
			{
				if(a[j] == 1)
				{
					val += dp[obs - j][0];
					// cerr << "add dp 0 " << obs - j << " : " << dp[obs - j][0] << '\n';
					j++;
				}
			}
 
			for(int h : a)
			{
				cerr << h;
			}
 
			// cerr << " -> ";
 
 
			// cerr << "sending val = " << val << '\n';
 
			for(int j = 0; j < cbs; j++)
				res.push_back(bool(val & pow2[j]));
		}
 
		// cerr << "res = ";
		// for(int y : res)
		// 	cerr << y;
		// cerr << '\n';
 
 
 
 
 
		return res;
	}	
}
 
 
 
void Anna(int N, vector<char> S)
{
	// cerr << "hello\n";
	int fx = 0;
	int lz = N-1;
 
	while(fx < N && S[fx] != 'X')
		fx++;
 
	while(lz >= 0 && S[lz] != 'Z')
		lz--;
 
	if(fx == N || lz == -1 || fx >= lz)
	{
		// cerr << "hello2\n";
		return;
	}
 
	vi tosend(N+1, 0);
 
	tosend[fx] = 1;
	tosend[lz+1] = 1;
 
	for(int i = fx+2; i <= lz-1; i++)
	{
		if(S[i-1] == 'Z' && S[i] == 'Y')
			tosend[i] = 1;
	}
 
	for(int i = 0; i+1 < sz(tosend); i++)
		assert(!(tosend[i] == 1 && tosend[i+1] == 1));
 
	// for(int i = 0; i <= N; i++)
	// 	cerr << tosend[i];
	// cerr << '\n';
 
	tosend = encode(tosend);
 
	for(int f : tosend)
		Send(f);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
 
namespace
{
	using namespace std;
 
	using vi = vector<int>;
	using pii = pair<int, int>;
	using vpii = vector<pii>;
	using ll = long long;
	using vll = vector<ll>;
	#define sz(x) int(x.size())
 
 
	const int obs = 76;
	const int cbs = 53;
 
 
	vi decode(vi A, int S) //S = size of decoded sequence
	{
		// cerr << "\n\n\n decoding\n";
		assert(sz(A) % cbs == 0);
 
		vi res;
		
		for(int i = 0; i < sz(A); i += cbs)
		{
			vll a;
			for(int j = i; j < i+cbs; j++)
				a.push_back(A[j]);
 
 
			ll pow2[cbs];
			pow2[0] = 1;
			for(int i = 1; i < cbs; i++)
				pow2[i] = pow2[i-1] * 2LL;
 
 
			ll val = 0;
			for(int j = 0; j < cbs; j++)
				val += pow2[j] * a[j];
 
			// cerr << "val = " << val << '\n';
 
 
			ll dp[1 + obs][2];
 
			dp[1][0] = 1;
			dp[1][1] = 1;
 
			for(int i = 2; i <= obs; i++)
			{
				dp[i][0] = dp[i-1][0] + dp[i-1][1];
				dp[i][1] = dp[i-1][0];
			}
 
		// 	cerr << "dp values: \n";
		// for(int i = 1; i <= obs; i++)
		// 	cerr << dp[i][0] << ' ' << dp[i][1] << '\n';
 
			vi cres;
 
 
			for(int j = 0; j < obs; j++)
			{
				if(dp[obs - j][0] > val)
					cres.push_back(0);
				else
				{
					val -= dp[obs - j][0];
					cres.push_back(1);
					if(j != obs - 1)
						cres.push_back(0);
					j++;
				}
			}
 
			// cerr << "cres = ";
			// for(int c : cres)
			// 	cerr << c;
			// cerr << "\n";
 
			for(int c : cres)
				res.push_back(c);
 
			assert(val == 0);
		}
 
 
		// cerr << "decoded : ";
		// for(int r : res)
		// 	cerr << r;
		// cerr << '\n';
 
		while(sz(res) > S)
			res.pop_back();
 
		// cerr << "after resizing : ";
		// for(int r : res)
		// 	cerr << r;
		// cerr << '\n';
 
 
		return res;
	}
}
 
 
void Bruno(int N, int L, vi A)
{
 
	if(A.empty())
	{
		for(int i = 0; i < N; i++)
			Remove(i);
 
		return;
	}
 
	A = decode(A, N+1);
 
	assert(sz(A) == N+1);
 
	int lz = N;
	while(A[lz] != 1)
		lz--;
	lz--;
 
	int fx = 0;
	while(A[fx] != 1)
		fx++;
 
	// cerr << fx << ' ' << lz << '\n';
 
	while(!(0 <= fx && fx < lz && lz < N));
 
	for(int i = 0; i < fx; i++)
		Remove(i);
	for(int i = lz+1; i < N; i++)
		Remove(i);
 
	vi st;
 
	for(int i = fx+1; i <= lz; i++)
	{
		if(i < lz && A[i+1] == 0)
		{
			// cerr << "add " << i << " to stack\n";
			st.push_back(i);
		}
		else
		{
			while(!st.empty())
			{
				Remove(st.back());
				// cerr << "pop " << st.back() << '\n';
				st.pop_back();
			}
			Remove(i);
			// cerr << "remove Z : " << i << '\n';
		}
	}
 
	Remove(fx);
	// cerr << "final remove " << fx << '\n';
}

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