Submission #458881

#	Time	Username	Problem	Language	Result	Execution time	Memory
458881		8e7	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	69 ms	7992 KiB

Anna

//Challenge: Accepted
#include "Anna.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second

namespace{
	ll fib[65];
}

void Anna(int N, vector<char> S) {
	fib[0] = fib[1] = 1;
	for (int i = 2;i < 64;i++) fib[i] = fib[i - 1] + fib[i - 2];	
	vector<int> bit (N, 0);
	bool found = 0;
	int first = 0;
	for (int i = 0;i < N;i++) {
		if (S[i] == 'X' && !found) {
			found = 1;
			first = i;
			bit[i] = 1;
		}
		if (found && first != i - 1 && S[i] == 'Z' && (i == N - 1 || S[i + 1] != 'Z')) {
			bit[i] = 1;
		}	
	}
	for (int i = 0;i < N;i+=63){
		ll send = 0;
		for (int j = 0;j < 63;j++) send += fib[j+1] * (i + j < N ? bit[i+j] : 0);
		for (int j = 0;j < 44;j++) {
			Send((send & (1LL<<j)) ? 1 : 0);
		}
	}	
	if (found && first < N - 1 && S[first + 1] == 'Z') Send(1);
	else Send(0);
}
/*
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp
*/

Bruno

//Challenge: Accepted
#include "Bruno.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second


namespace {
	ll fib[65];

}  // namespace

void Bruno(int N, int L, vector<int> A) {
	fib[0] = fib[1] = 1;
	for (int i = 2;i < 64;i++) fib[i] = fib[i - 1] + fib[i - 2];	

	vector<int> v;
	for (int i = 0;i < L - 1;i += 44) {
		ll num = 0;
		for (int j = 0;j < 44;j++) num += ((ll)A[i+j])<<j;
		vector<int> tmp;
		for (int j = 63;j > 0;j--) {
			if (num >= fib[j]) {
				num -= fib[j];
				tmp.push_back(1);
			} else{
				tmp.push_back(0);	
			}
		}
		reverse(tmp.begin(), tmp.end());
		v.insert(v.end(), tmp.begin(), tmp.end());
	}	
	int ch = A.back();
	bool found = 0;
	int first = 0;
	for (int i = 0;i < N;i++) {
		if (v[i]) {
			for (int j = i - 1;j >= 0;j--) {
				if (v[j]) break;
				Remove(j);
			}
			if (!found) found = 1, first = i;
			else Remove(i);
		} else if (found && ch && i == first + 1) {
			Remove(i);
			v[i] = 1;
		}
	}
	for (int j = N - 1;j >= 0;j--) {
		if (v[j]) break;
		Remove(j);
	}
	if (found) Remove(first);
}
/*
5
X Y Z Y Z
*/

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95