Submission #1153850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153850		KickingKun	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	48 ms	6416 KiB

Anna

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

using namespace std;

void Anna(int N, vector<char> S) {
	int initN = N;
	for (int i = 0; i < N - 1; i++) {
		if (S[i] == 'Z' && S[i + 1] == 'Z') S[i] = 'Y';
	}
	
	int idX = N;
	for (int i = 0; i < N; i++) if (S[i] == 'X') {
		idX = i; break;
	}
	
	bool tail;
	if (idX < N - 1 && S[idX + 1] == 'Z') {
		tail = true; S[idX + 1] = 'Y';
	}
	else tail = false;
	
	while (N % 64 != 0) S.emplace_back('Y'), ++N;
	
	vector <bool> init(N);
	int p = 0; while (p < N && S[p] != 'X') init[p] = 0, ++p;
	while (p < N) {
		init[p] = 1; ++p;
		while (p < N && S[p] != 'Z') init[p] = 0, ++p;
	}
	
//	for (int i = 0; i < N; i++)
//		cerr << init[i] << ' ';
//	cerr << '\n';
	
	vector <long long> fibo(63);
	fibo[0] = 1; fibo[1] = 2;
	for (int i = 2; i < 63; i++)
		fibo[i] = fibo[i - 1] + fibo[i - 2];

	for (int i = 0; i < N; i += 63) {
		long long order = 0;
		for (int j = i; j < i + 63; j++)
			if (init[j]) order += fibo[i + 62 - j];
		
		for (int bits = 43; bits >= 0; bits--) {
			Send((order >> bits) & 1);
//			cerr << ((order >> bits) & 1) << ' ';
		}
//		cerr << '\n' << order << '\n';
	}
	Send(tail);
}

Bruno

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

using namespace std;

void Bruno(int N, int L, vector<int> A) {
	bool tail = A.back();
	
	vector <long long> fibo(63);
	fibo[0] = 1; fibo[1] = 2;
	for (int i = 2; i < 63; i++)
		fibo[i] = fibo[i - 1] + fibo[i - 2];
		
	vector <int> decode;
	for (int i = 0; i < L; i += 44) {
		long long num = 0;
		for (int j = i; j <= i + 43; j++)
			num = num * 2 + A[j];
		
//		cerr << '\n' << num << '\n';
		for (int j = 62; j >= 0; j--) {
			if (num >= fibo[j]) {
				decode.emplace_back(1);
				num -= fibo[j];
			}
			else decode.emplace_back(0);
		}
	}
	
	if (tail) {
		for (int i = 0; i < N; i++) if (decode[i]) {
			decode[i + 1] = true;
			break;
		}
	}
	
//	for (int i = 0; i < N; i++)
//		cerr << decode[i] << ' ';
//	cerr << '\n';
	
	int fir = 0; while (fir < N && decode[fir] == 0) ++fir;
	for (int pos = fir + 1; pos < N;) {
		int st = pos; while (pos < N && decode[pos] == 0) ++pos;
		for (int i = pos - 1; i >= st; i--) Remove(i);
		if (pos < N) Remove(pos), ++pos;
	}
	for (int i = 0; i < fir; i++) Remove(i);
	if (fir < N) Remove(fir);
}

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