Submission #387982

#	Time	Username	Problem	Language	Result	Execution time	Memory
387982		keko37	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	91 ms	8396 KiB

Anna

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

using namespace std;

typedef long long llint;

const int MAXN = 90;
const int SIZ = 63;

llint fib[MAXN];

int get_bits (llint val) {
	int res = 0;
	llint pot = 1;
	for (int i = 0; i < 50; i++) {
		if (val & pot) res = i + 1;
		pot *= 2;
	}
	return res;
}

void precompute () {
	fib[0] = 0; fib[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
}

void send_num (llint val, int br) {
	llint pot = 1;
	for (int i = 0; i < br; i++) {
		if (val & pot) Send(1); else Send(0);
		pot *= 2;
	}
}

llint compress (vector <int> v) {
	int n = 0;
	for (auto x : v) n += x;
	llint res = 1;
	for (auto x : v) {
		if (x == 1) {
			n--;
		} else {
			res += fib[n];
			n -= 2;
		}
	}
	return res;
}

void Anna (int N, vector <char> S) {
	precompute();
	int lef = N, rig = N;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'X') {
			lef = i;
			break;
		}
	}
	for (int i = N-1; i >= 0; i--) {
		if (S[i] == 'Z') {
			rig = i;
			break;
		}
	}
	send_num(lef, 17);
	send_num(rig, 17);
	
	vector <int> r((SIZ + 1) / 2, 2);
	int bits = get_bits(compress(r));
	
	vector <int> v;
	for (int i = 0; i < N; i++) {
		if (i + 1 < N && S[i] == 'Y' && S[i + 1] == 'X') {
			v.push_back(2);
			i++;
		} else {
			v.push_back(1);
		}
	}
	vector <int> tmp;
	int sum = 0;
	for (auto x : v) {
		tmp.push_back(x);
		sum += x;
		if (sum >= SIZ) {
			if (sum == SIZ) tmp.push_back(1);
			send_num(compress(tmp), bits);
			tmp.clear();
			sum = 0;
		}
	}
	if (!tmp.empty()) {
		while (sum < SIZ + 1) {
			tmp.push_back(1);
			sum++;
		}
		send_num(compress(tmp), bits);
	}
}

Bruno

#include<bits/stdc++.h>
#include "Bruno.h"
#include <vector>

using namespace std;

typedef long long llint;

const int MAXN = 90;
const int SIZ = 63;

llint fib_bruno[MAXN];
int a_pos;
vector <int> a;

int get_bits_bruno (llint val) {
	int res = 0;
	llint pot = 1;
	for (int i = 0; i < 50; i++) {
		if (val & pot) res = i + 1;
		pot *= 2;
	}
	return res;
}

void precompute_bruno () {
	fib_bruno[0] = 0; fib_bruno[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		fib_bruno[i] = fib_bruno[i - 1] + fib_bruno[i - 2];
	}
}

llint get_num (int br) {
	llint res = 0;
	llint pot = 1;
	for (int i = 0; i < br; i++) {
		res += pot * a[a_pos];
		a_pos++;
		pot *= 2;
	}
	return res;
}

llint compress_bruno (vector <int> v) {
	int n = 0;
	for (auto x : v) n += x;
	llint res = 1;
	for (auto x : v) {
		if (x == 1) {
			n--;
		} else {
			res += fib_bruno[n];
			n -= 2;
		}
	}
	return res;
}

vector <int> decompress (llint val) {
	vector <int> v;
	int n = SIZ + 1;
	while (n > 0) {
		if (val > fib_bruno[n]) {
			val -= fib_bruno[n];
			v.push_back(2);
			n -= 2;
		} else {
			v.push_back(1);
			n--;
		}
	}
	return v;
}

void ispis (vector <int> v) {
	for (auto x : v) cout << x << " "; cout << endl;
}

void Bruno (int N, int L, vector <int> A) {
	a = A;

	precompute_bruno();
	vector <int> r((SIZ + 1) / 2, 2);
	int bits = get_bits_bruno(compress_bruno(r));
	
	int lef = get_num(17);
	int rig = get_num(17);
	
	vector <int> v;
	while (a_pos < L) {
		llint val = get_num(bits);
		vector <int> tmp = decompress(val);
		if (tmp.back() == 1) tmp.pop_back();
		for (auto x : tmp) {
			if (x == 1) v.push_back(1);
			if (x == 2) v.push_back(0), v.push_back(0);
		}
	}
	
	v[lef] = 0; v[rig] = 0;
	
	for (int i = 0; i < N; i++) {
		if (v[i] == 1) Remove(i);
	}
	for (int i = N - 1; i >= 0; i--) {
		if (i == lef || i == rig) continue;
		if (v[i] == 0) Remove(i);
	}
	if (lef < N) Remove(lef);
	if (rig < N) Remove(rig);
}

Compilation message (stderr)

Bruno.cpp: In function 'void ispis(std::vector<int>)':
Bruno.cpp:76:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |  for (auto x : v) cout << x << " "; cout << endl;
      |  ^~~
Bruno.cpp:76:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |  for (auto x : v) cout << x << " "; cout << endl;
      |                                     ^~~~

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