Submission #664556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
664556	2022-11-27T07:47:55 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	1428 ms	11356 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	1 ms	516 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	1 ms	508 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	1 ms	516 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	0 ms	516 KB	Output is correct
9	Correct	0 ms	508 KB	Output is correct
10	Correct	2 ms	508 KB	Output is correct
11	Correct	0 ms	508 KB	Output is correct

Subtask #2

64.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1428 ms	11000 KB	Partially correct
2	Partially correct	1382 ms	11068 KB	Partially correct
3	Partially correct	1310 ms	10996 KB	Partially correct
4	Partially correct	1283 ms	11356 KB	Partially correct
5	Partially correct	1260 ms	11148 KB	Partially correct
6	Partially correct	1319 ms	11152 KB	Partially correct
7	Partially correct	1303 ms	11068 KB	Partially correct
8	Partially correct	1339 ms	11104 KB	Partially correct
9	Partially correct	1378 ms	10824 KB	Partially correct
10	Partially correct	1357 ms	11052 KB	Partially correct
11	Partially correct	1254 ms	10744 KB	Partially correct
12	Partially correct	1273 ms	11096 KB	Partially correct
13	Partially correct	1284 ms	11284 KB	Partially correct
14	Partially correct	1297 ms	11208 KB	Partially correct
15	Partially correct	1341 ms	10976 KB	Partially correct
16	Partially correct	1307 ms	11088 KB	Partially correct
17	Correct	43 ms	6444 KB	Output is correct
18	Correct	44 ms	6432 KB	Output is correct
19	Correct	44 ms	6376 KB	Output is correct
20	Partially correct	1353 ms	11112 KB	Partially correct
21	Partially correct	1347 ms	11052 KB	Partially correct
22	Partially correct	1342 ms	11128 KB	Partially correct
23	Partially correct	1295 ms	11020 KB	Partially correct
24	Partially correct	1325 ms	11144 KB	Partially correct
25	Correct	53 ms	6432 KB	Output is correct
26	Correct	43 ms	6416 KB	Output is correct
27	Correct	41 ms	6436 KB	Output is correct
28	Correct	56 ms	6376 KB	Output is correct
29	Correct	49 ms	6284 KB	Output is correct
30	Correct	49 ms	6432 KB	Output is correct
31	Correct	48 ms	6256 KB	Output is correct
32	Partially correct	1284 ms	11088 KB	Partially correct
33	Partially correct	1272 ms	11092 KB	Partially correct