Submission #419799

#	Time	Username	Problem	Language	Result	Execution time	Memory
419799		amoo_safar	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	84 ms	9820 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int bl = 76;
const int Log = 53;
ll fib[bl];

void Send(vector<int> seq){
	while((int) seq.size() % bl != 0)
		seq.pb(0);
	ll cd = 0;
	for(int i = 0; i < (int) seq.size(); i += bl){
		int j = i + bl - 1;
		while(i <= j){
			if(seq[j] == 0){
				j--;
				continue;
			}
			cd += fib[j - i];
			j -= 2;
		}
		// cerr << "Sent : " << cd << '\n';
		// cerr << "SEQ : ";
		// for(int j = i; j < i + bl; j++) cerr << seq[j];
		// cerr << '\n';
		for(int c = 0; c < Log; c++){
			Send(cd & 1);
			cd >>= 1;
		}
	}
}

void Anna(int _n, vector<char> S){
	fib[0] = 1;
	fib[1] = 2;
	for(int i = 2; i < bl; i++) fib[i] = fib[i - 1] + fib[i - 2];

	vector<int> V(_n, 0), seq;
	int fl = 0, fly = 1;
	for(int i = _n - 1; i >= 0; i--){
		if(S[i] == 'Y') fly = 1;
		if(S[i] == 'Z' && fly == 1)
			V[i] = 1, fly = 0;
	}
	int i = 0;
	for(auto c : S){
		if(fl == 0 && c == 'X'){
			fl = 1;
			seq.pb(1);
			seq.pb(0);
		} else {
			seq.pb(fl ? V[i] : 0);
		}
		i ++;
	}
	Send(seq);
	// for(auto x : seq)
		// Send(x);
	// for(auto x : seq)
		// cerr << x;
	// cerr << '\n';
	
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int bl = 76;
const int Log = 53;
ll fib2[bl];


void Bruno(int _n, int L, vector<int> C) {
	fib2[0] = 1;
	fib2[1] = 2;
	for(int i = 2; i < bl; i++) fib2[i] = fib2[i - 1] + fib2[i - 2];
	
	vector<int> B;
	for(int i = 0; i < L; i += Log){
		ll nw = 0;
		for(int j = i + Log - 1; j >= i; j--){
			nw = nw + nw + C[j];
		}
		// cerr << "Got : " << nw << '\n';
		int ln = bl;
		vector<int> V;
		while(ln > 0){
			if(nw >= fib2[ln - 1]){
				nw -= fib2[ln - 1];
				V.pb(1);
				ln --;
				if(ln)
					V.pb(0);
				ln --;
			} else {
				V.pb(0);
				ln --;
			}
		}
		reverse(V.begin(), V.end());
		for(auto x : V)
			B.pb(x);
	}
	
	// cerr << "!! ";
	// for(auto x : B) cerr << x; cerr << '\n'; 
	B.resize(_n + 1);
	L = B.size();
	for(int i = 0; i + 1 < L; i++)
		assert((B[i] == 0) || (B[i + 1] == 0));

	int fl = 0;
	vector<int> A;
	for(int i = 0; i < L; i++){
		if(B[i] == 0) A.pb(0);
		else {
			A.pb(1);
			if(!fl) i++;
			fl = 1;
		}
	}
	A.resize(_n, 0);
	L = _n;

	int cnt = 0;
	vector<int> mk(_n, 0);
	for (int i = 0; i < L; i++) {
		// cerr << "!" << A[i] << '\n';
		if(A[i] == 1){
			cnt ++;
			for(int j = i - 1; j >= 0; j--){
				if(A[j] == 1) break;
				Remove(j);
				mk[j] = 1;
			}
			if(cnt != 1){
				Remove(i);
				mk[i] = 1;
			};
		}
	}
	for(int i = 0; i < _n; i++) if(!mk[i]) Remove(i);
}

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