Submission #664461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
664461	2022-11-27T07:34:13 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	64 / 100	2000 ms	8292 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 = 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);
}

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

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

Compilation message

Anna.cpp:18:5: warning: '{anonymous}::vi {anonymous}::encode({anonymous}::vi)' defined but not used [-Wunused-function]
   18 |  vi encode(vi A)
      |     ^~~~~~

Bruno.cpp:20:5: warning: '{anonymous}::vi {anonymous}::decode({anonymous}::vi, int)' defined but not used [-Wunused-function]
   20 |  vi decode(vi A, int S) //S = size of decoded sequence
      |     ^~~~~~

Subtask #1

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	0 ms	512 KB	Output is correct
4	Correct	0 ms	508 KB	Output is correct
5	Correct	1 ms	512 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	2079 ms	508 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2

64.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	49 ms	8040 KB	Partially correct
2	Partially correct	49 ms	8088 KB	Partially correct
3	Partially correct	48 ms	7996 KB	Partially correct
4	Partially correct	47 ms	8012 KB	Partially correct
5	Partially correct	49 ms	8064 KB	Partially correct
6	Partially correct	53 ms	8040 KB	Partially correct
7	Partially correct	49 ms	7988 KB	Partially correct
8	Partially correct	56 ms	8112 KB	Partially correct
9	Partially correct	49 ms	8040 KB	Partially correct
10	Partially correct	48 ms	7968 KB	Partially correct
11	Partially correct	50 ms	8032 KB	Partially correct
12	Partially correct	49 ms	8040 KB	Partially correct
13	Partially correct	55 ms	8164 KB	Partially correct
14	Partially correct	60 ms	8072 KB	Partially correct
15	Partially correct	55 ms	8176 KB	Partially correct
16	Partially correct	52 ms	8024 KB	Partially correct
17	Correct	41 ms	6404 KB	Output is correct
18	Correct	40 ms	6428 KB	Output is correct
19	Correct	43 ms	6496 KB	Output is correct
20	Partially correct	46 ms	8048 KB	Partially correct
21	Partially correct	48 ms	8128 KB	Partially correct
22	Partially correct	55 ms	8292 KB	Partially correct
23	Partially correct	49 ms	8000 KB	Partially correct
24	Partially correct	48 ms	7956 KB	Partially correct
25	Correct	42 ms	6308 KB	Output is correct
26	Correct	43 ms	6372 KB	Output is correct
27	Partially correct	55 ms	8188 KB	Partially correct
28	Correct	41 ms	6384 KB	Output is correct
29	Correct	43 ms	6432 KB	Output is correct
30	Correct	43 ms	6372 KB	Output is correct
31	Correct	40 ms	6516 KB	Output is correct
32	Partially correct	49 ms	8048 KB	Partially correct
33	Partially correct	49 ms	8088 KB	Partially correct