oj.uz

Submission #664449

# Submission time Handle Problem Language Result Execution time Memory
664449 2022-11-27T07:31:56 Z blue Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 2000 ms 8792 KB 
#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 = 30;
	const int cbs = 30;

	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++;
				}
			}


			// cerr << "sending " << 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)
	{
		// 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 <= N; i++)
	// 	cerr << tosend[i];
	// cerr << '\n';

	tosend = encode(tosend);

	for(int f : tosend)
		Send(f);
}
#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 = 30;
	const int cbs = 30;


	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';


			for(int j = 0; j < obs; j++)
			{
				if(dp[obs - j][0] > val)
					res.push_back(0);
				else
				{
					val -= dp[obs - j][0];
					res.push_back(1);
					res.push_back(0);
					j++;
				}
			}

			assert(val == 0);
		}


		// cerr << "decoded : ";
		// for(int r : res)
		// 	cerr << r;
		// cerr << '\n';

		while(sz(res) > S)
			res.pop_back();


		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);

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 520 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 0 ms 520 KB Output is correct
5 Correct 0 ms 508 KB Output is correct
6 Correct 0 ms 508 KB Output is correct
7 Correct 0 ms 508 KB Output is correct
8 Execution timed out 2059 ms 516 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8792 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -