Submission #398155

#	Time	Username	Problem	Language	Result	Execution time	Memory
398155		ChrisT	Ancient Machine (JOI21_ancient_machine)	C++17	40 / 100	131 ms	9068 KiB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
const int MN = 1e6 + 5;
map<char,int> gg = {{'X',0},{'Y',1},{'Z',2}};	
void Anna (int n, vector<char> s) {
	for (int i = 0; i < n; i += 29) {
		//[i,i+29)
		int ed = min(i+29,n);
		long long val = 0, pw = 1;
		for (int j = i; j < ed; j++) {
			val += pw * gg[s[j]];
			pw *= 3;
		}
		for (int j = 0; j < 46; j++) Send(val >> j & 1);
	}
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
const int MN = 1e6 + 5;
map<int,char> gg = {{0,'X'},{1,'Y'},{2,'Z'}};
void Bruno (int n, int l, vector<int> a) {
	vector<char> s(n); reverse(a.begin(),a.end());
	for (int i = 0; i < n; i += 29) {
		int ed = min(i+29,n); long long val = 0;
		for (int j = 0; j < 46; j++) {
			val |= (((long long)a.back()) << j);
			a.pop_back();
		}
		for (int j = i; j < ed; j++) {
			s[j] = gg[val % 3];
			val /= 3;
		}
	}
	int st = 0;
	while (st < n && s[st] != 'X') Remove(st++);
	if (st == n) return;
	int ed = n-1;
	while (ed >= st && s[ed] != 'Z') Remove(ed--);
	vector<int> inds = {st}; bool found = false;
	vector<bool> dead(n);
	for (int i = st+1; i <= ed; i++) {
		if (s[i] != 'Y') Remove(i), dead[i] = true;
		else {
			found = true;
			break;
		}
	}
	if (!found) return;
	for (int i = ed-1; i >= st; i--) {
		if (s[i] != 'Y') Remove(i), dead[i] = true;
		else break;
	}
	for (int i = st + 1; i <= ed - 1; i++) {
		if (!dead[i] && !dead[i-1] && (s[i] == 'Y') == (s[i-1] == 'Y')) Remove(i-1), dead[i-1] = true;
	}
	set<int> xs,ys,zs;
	for (int i = st; i <= ed; i++) if (!dead[i]) {
		if (s[i] == 'X') xs.insert(i);
		else if (s[i] == 'Y') ys.insert(i);
		else zs.insert(i);
	}
	while (!ys.empty()) {
		int fz = *zs.begin();
		int lx = *prev(xs.upper_bound(fz));
		int my = *ys.lower_bound(lx);
		assert(lx <= my && my <= fz);
		Remove(my); ys.erase(my);
		if (fz != ed) Remove(fz), zs.erase(fz);
		else Remove(lx), xs.erase(lx);
	}
	for (int i : xs) Remove(i);
	for (int i : zs) Remove(i);
}

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