Submission #664680

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
664680	2022-11-27T08:13:17 Z	blue	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	187 ms	8736 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 = 80;
	const int cbs = 56;
 
	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 = 80;
	const int cbs = 56;
 
 
	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	508 KB	Output is correct
3	Correct	0 ms	516 KB	Output is correct
4	Correct	0 ms	508 KB	Output is correct
5	Correct	0 ms	508 KB	Output is correct
6	Correct	0 ms	508 KB	Output is correct
7	Correct	1 ms	508 KB	Output is correct
8	Correct	0 ms	508 KB	Output is correct
9	Correct	0 ms	508 KB	Output is correct
10	Correct	0 ms	508 KB	Output is correct
11	Correct	0 ms	516 KB	Output is correct

Subtask #2

94.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	170 ms	8520 KB	Partially correct
2	Partially correct	168 ms	8452 KB	Partially correct
3	Partially correct	169 ms	8456 KB	Partially correct
4	Partially correct	181 ms	8460 KB	Partially correct
5	Partially correct	164 ms	8612 KB	Partially correct
6	Partially correct	164 ms	8484 KB	Partially correct
7	Partially correct	163 ms	8692 KB	Partially correct
8	Partially correct	173 ms	8388 KB	Partially correct
9	Correct	187 ms	8520 KB	Output is correct
10	Correct	166 ms	8608 KB	Output is correct
11	Correct	168 ms	8736 KB	Output is correct
12	Correct	171 ms	8480 KB	Output is correct
13	Partially correct	178 ms	8696 KB	Partially correct
14	Partially correct	180 ms	8376 KB	Partially correct
15	Correct	172 ms	8576 KB	Output is correct
16	Correct	180 ms	8592 KB	Output is correct
17	Correct	45 ms	6380 KB	Output is correct
18	Correct	44 ms	6440 KB	Output is correct
19	Correct	47 ms	6448 KB	Output is correct
20	Partially correct	167 ms	8472 KB	Partially correct
21	Partially correct	165 ms	8400 KB	Partially correct
22	Partially correct	174 ms	8660 KB	Partially correct
23	Correct	166 ms	8708 KB	Output is correct
24	Correct	166 ms	8364 KB	Output is correct
25	Correct	43 ms	6424 KB	Output is correct
26	Correct	44 ms	6520 KB	Output is correct
27	Correct	44 ms	6524 KB	Output is correct
28	Correct	45 ms	6388 KB	Output is correct
29	Correct	48 ms	6416 KB	Output is correct
30	Correct	45 ms	6448 KB	Output is correct
31	Correct	47 ms	6452 KB	Output is correct
32	Partially correct	168 ms	8532 KB	Partially correct
33	Partially correct	176 ms	8364 KB	Partially correct