Submission #664616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
664616	2022-11-27T07:57:48 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	219 ms	8796 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 = 42;
 
	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 = 42;
 
 
	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	0 ms	516 KB	Output is correct
2	Correct	1 ms	516 KB	Output is correct
3	Correct	1 ms	516 KB	Output is correct
4	Correct	1 ms	508 KB	Output is correct
5	Correct	1 ms	508 KB	Output is correct
6	Correct	1 ms	508 KB	Output is correct
7	Correct	1 ms	516 KB	Output is correct
8	Correct	1 ms	516 KB	Output is correct
9	Correct	0 ms	516 KB	Output is correct
10	Correct	0 ms	508 KB	Output is correct
11	Correct	0 ms	508 KB	Output is correct

Subtask #2

94.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	165 ms	8444 KB	Partially correct
2	Partially correct	169 ms	8440 KB	Partially correct
3	Partially correct	166 ms	8380 KB	Partially correct
4	Partially correct	165 ms	8476 KB	Partially correct
5	Partially correct	166 ms	8428 KB	Partially correct
6	Partially correct	166 ms	8432 KB	Partially correct
7	Partially correct	164 ms	8468 KB	Partially correct
8	Partially correct	162 ms	8420 KB	Partially correct
9	Partially correct	160 ms	8408 KB	Partially correct
10	Partially correct	159 ms	8548 KB	Partially correct
11	Partially correct	184 ms	8508 KB	Partially correct
12	Partially correct	168 ms	8496 KB	Partially correct
13	Partially correct	175 ms	8672 KB	Partially correct
14	Partially correct	178 ms	8432 KB	Partially correct
15	Partially correct	172 ms	8796 KB	Partially correct
16	Partially correct	170 ms	8600 KB	Partially correct
17	Correct	43 ms	6444 KB	Output is correct
18	Correct	41 ms	6348 KB	Output is correct
19	Correct	44 ms	6396 KB	Output is correct
20	Partially correct	161 ms	8328 KB	Partially correct
21	Partially correct	162 ms	8540 KB	Partially correct
22	Partially correct	173 ms	8676 KB	Partially correct
23	Partially correct	219 ms	8420 KB	Partially correct
24	Partially correct	176 ms	8424 KB	Partially correct
25	Correct	44 ms	6348 KB	Output is correct
26	Correct	51 ms	6408 KB	Output is correct
27	Correct	45 ms	6400 KB	Output is correct
28	Correct	44 ms	6456 KB	Output is correct
29	Correct	43 ms	6408 KB	Output is correct
30	Correct	49 ms	6256 KB	Output is correct
31	Correct	44 ms	6272 KB	Output is correct
32	Partially correct	176 ms	8468 KB	Partially correct
33	Partially correct	165 ms	8536 KB	Partially correct