답안 #664562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
664562	2022-11-27T07:48:58 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	242 ms	9120 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 = 60;
	const int cbs = 60;

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


	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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	508 KB	Output is correct
2	Correct	1 ms	516 KB	Output is correct
3	Correct	0 ms	516 KB	Output is correct
4	Correct	0 ms	508 KB	Output is correct
5	Correct	2 ms	516 KB	Output is correct
6	Correct	1 ms	508 KB	Output is correct
7	Correct	1 ms	508 KB	Output is correct
8	Correct	0 ms	520 KB	Output is correct
9	Correct	0 ms	508 KB	Output is correct
10	Correct	1 ms	516 KB	Output is correct
11	Correct	0 ms	508 KB	Output is correct

Subtask #2

64.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	172 ms	8792 KB	Partially correct
2	Partially correct	171 ms	8768 KB	Partially correct
3	Partially correct	169 ms	8776 KB	Partially correct
4	Partially correct	169 ms	8736 KB	Partially correct
5	Partially correct	170 ms	8712 KB	Partially correct
6	Partially correct	195 ms	8660 KB	Partially correct
7	Partially correct	199 ms	8776 KB	Partially correct
8	Partially correct	242 ms	8796 KB	Partially correct
9	Partially correct	184 ms	8640 KB	Partially correct
10	Partially correct	184 ms	8816 KB	Partially correct
11	Partially correct	181 ms	8772 KB	Partially correct
12	Partially correct	176 ms	8768 KB	Partially correct
13	Partially correct	196 ms	9040 KB	Partially correct
14	Partially correct	195 ms	8800 KB	Partially correct
15	Partially correct	181 ms	9004 KB	Partially correct
16	Partially correct	183 ms	8820 KB	Partially correct
17	Correct	51 ms	6428 KB	Output is correct
18	Correct	44 ms	6268 KB	Output is correct
19	Correct	43 ms	6480 KB	Output is correct
20	Partially correct	181 ms	8696 KB	Partially correct
21	Partially correct	185 ms	8704 KB	Partially correct
22	Partially correct	180 ms	8836 KB	Partially correct
23	Partially correct	189 ms	8728 KB	Partially correct
24	Partially correct	218 ms	9120 KB	Partially correct
25	Correct	41 ms	6496 KB	Output is correct
26	Correct	43 ms	6428 KB	Output is correct
27	Correct	44 ms	6480 KB	Output is correct
28	Correct	43 ms	6456 KB	Output is correct
29	Correct	41 ms	6384 KB	Output is correct
30	Correct	43 ms	6420 KB	Output is correct
31	Correct	41 ms	6400 KB	Output is correct
32	Partially correct	196 ms	8820 KB	Partially correct
33	Partially correct	189 ms	8772 KB	Partially correct