Submission #664560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
664560	2022-11-27T07:48:42 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	215 ms	9004 KB

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 = 2;
	const int cbs = 2;

	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 = 2;
	const int cbs = 2;


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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	0 ms	516 KB	Output is correct
3	Correct	0 ms	508 KB	Output is correct
4	Correct	1 ms	516 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	516 KB	Output is correct
8	Correct	0 ms	512 KB	Output is correct
9	Correct	0 ms	508 KB	Output is correct
10	Correct	0 ms	508 KB	Output is correct
11	Correct	1 ms	508 KB	Output is correct

Subtask #2

64.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	178 ms	8784 KB	Partially correct
2	Partially correct	176 ms	8764 KB	Partially correct
3	Partially correct	180 ms	9004 KB	Partially correct
4	Partially correct	179 ms	8732 KB	Partially correct
5	Partially correct	178 ms	8688 KB	Partially correct
6	Partially correct	184 ms	8824 KB	Partially correct
7	Partially correct	190 ms	8736 KB	Partially correct
8	Partially correct	209 ms	8724 KB	Partially correct
9	Partially correct	191 ms	8448 KB	Partially correct
10	Partially correct	182 ms	8792 KB	Partially correct
11	Partially correct	191 ms	8436 KB	Partially correct
12	Partially correct	190 ms	8776 KB	Partially correct
13	Partially correct	189 ms	8864 KB	Partially correct
14	Partially correct	196 ms	8756 KB	Partially correct
15	Partially correct	193 ms	8808 KB	Partially correct
16	Partially correct	214 ms	8768 KB	Partially correct
17	Correct	48 ms	6360 KB	Output is correct
18	Correct	46 ms	6384 KB	Output is correct
19	Correct	49 ms	6336 KB	Output is correct
20	Partially correct	202 ms	8716 KB	Partially correct
21	Partially correct	200 ms	8744 KB	Partially correct
22	Partially correct	215 ms	8992 KB	Partially correct
23	Partially correct	202 ms	8704 KB	Partially correct
24	Partially correct	182 ms	8740 KB	Partially correct
25	Correct	45 ms	6380 KB	Output is correct
26	Correct	50 ms	6404 KB	Output is correct
27	Correct	47 ms	6352 KB	Output is correct
28	Correct	44 ms	6444 KB	Output is correct
29	Correct	46 ms	6436 KB	Output is correct
30	Correct	57 ms	6248 KB	Output is correct
31	Correct	55 ms	6340 KB	Output is correct
32	Partially correct	201 ms	8772 KB	Partially correct
33	Partially correct	204 ms	8764 KB	Partially correct