Submission #416952

#	Time	Username	Problem	Language	Result	Execution time	Memory
416952		oolimry	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	86 ms	8800 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

const int bin = 44, fib = 63;

vector<int> tosend;

lint dp[64];
void fibtobin(vector<int> F){
	lint res = 0;
	for(int i = 0;i < fib;){
		if(F[i] == 1){
			res += dp[fib-i-1];
			i += 2;
		}
		else i++;
	}
	
	for(int i = 0;i < bin;i++){
		tosend.push_back(res&1);
		res >>= 1;
	}
}

void Anna(int n, vector<char> s){	
	int X = -1;
	for(int i = 0;i < n;i++){
		if(s[i] == 'X'){
			X = i;
			break;
		}
	}
	
	dp[0] = 1, dp[1] = 2;
	for(int i = 2;i <= fib;i++) dp[i] = dp[i-1] + dp[i-2];
	if(X == -1) return;
	
	vector<int> original;
	for(int i = X+1;i < n;i++){
		if(s[i] == 'Z'){
			if(not original.empty() and original.back() == 1) original.back() = 0;
			original.push_back(1);
		}
		else original.push_back(0);
	}
	
	while(sz(original) % fib != 0) original.insert(original.begin(), 0);
	
	for(int i = 0;i < sz(original);i += fib){
		vector<int> f;
		for(int j = 0;j < fib;j++) f.push_back(original[i+j]);
		fibtobin(f);
	}
	
	for(int i = 0;i < 18;i++){
		tosend.push_back(X&1);
		X >>= 1;
	}
	
	for(int x : tosend) Send(x);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

int nn;
int vis[100005];
void rem(int i){
	if(i > nn) return;
	Remove(i); vis[i] = 1;
}

lint DP[64];
vector<int> bintofib(vector<lint> B){
	lint res = 0;
	reverse(all(B));
	for(int x : B){
		res *= 2;
		res += x;
	}
	
	vector<int> F;
	
	for(int i = 0;i < 63;){
		if(res >= DP[63-i-1]){
			res -= DP[63-i-1];
			F.push_back(1);
			if(i != 63-1) F.push_back(0);
			i += 2;
		}
		else{
			i++;
			F.push_back(0);
		}
	}
	
	return F;
}

void Bruno(int n, int L, vector<int> A){
	nn = n;
	
	if(sz(A) == 0){
		for(int i = 0;i < n;i++) Remove(i);
		return;
	}
	
	DP[0] = 1, DP[1] = 2;
	for(int i = 2;i <= 63;i++) DP[i] = DP[i-1] + DP[i-2];
	
	int X = 0;
	for(int i = 0;i < 18;i++){
		X *= 2;
		X += A.back();
		A.pop_back();
	}
	
	vector<int> C;
	for(int i = 0;i < sz(A);i += 44){
		vector<lint> b;
		for(int j = 0;j < 44;j++) b.push_back(A[i+j]);
		
		vector<int> f = bintofib(b);
		for(int x : f) C.push_back(x);
	}
	
	while(sz(C) > n-X-1) C.erase(C.begin());
	
	int prev = X+1;
	for(int i = X+1;i < n;i++){
		int c = C[i-X-1];
		if(c == 1){
			for(int j = i-1;j >= prev;j--) rem(j);
			rem(i);
			prev = i+1;
		}
	}
	
	for(int i = 0;i < n;i++){
		if(not vis[i]) rem(i);
	}
}

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