Submission #523087

#	Time	Username	Problem	Language	Result	Execution time	Memory
523087		amunduzbaev	Ancient Machine (JOI21_ancient_machine)	C++17	0 / 100	59 ms	10600 KiB

Anna

#include "Anna.h"
#include "bits/stdc++.h"
using namespace std;

#define ar array

void Anna(int n, vector<char> s) {
	vector<int> res(n);
	ar<int, 3> last {n, n, n};
	vector<ar<int, 3>> par(n + 1); par[n] = last;
	vector<ar<int, 3>> rap(n); 
	for(int i=n-1;~i;i--){
		last[s[i] - 'X'] = i;
		par[i] = last;
	}
	
	last[0] = last[1] = last[2] = -1;
	for(int i=0;i<n;i++){
		last[s[i] - 'X'] = i;
		rap[i] = last;
	}
	
	int i = par[0][0];
	vector<int> tt, tmp;
	if(i < n){
		int j = i; tt.push_back(i);
		while(j < n){
			j = par[j][1];
			int l = par[j][2];
			if(l < n){
				tt.push_back(j);
				tt.push_back(l);
			} j = l;
		}
	} i = rap[n - 1][2];
	if(~i){
		int j = i; tmp.push_back(i);
		while(~j){
			j = rap[j][1];
			if(~j){
				int l = rap[j][0];
				if(~l){
					tmp.push_back(j);
					tmp.push_back(l);
				} j = l;
			}
		}
	}
	
	int l = (int)tmp.size() - 1;
	ar<int, 2> r {l / 2, 0};
	for(int i=2;i<(int)tt.size();i++){
		while(l>=0 && tmp[l] <= tt[i]) l = max(l - 2, -1);
		r = max(r, {i / 2 + l / 2, i + 1});
	}
	
	for(int j=0;j<20;j++) Send(r[1] >> j & 1);
	
	for(int i=0;i<r[1];i++){
		res[tt[i]] = 1;
	}
	for(int i=0;i<(int)tmp.size();i++){
		if(r[1] && tmp[i] <= tt[r[1] - 1]) break;
		res[tmp[i]] = 1;
	}
	
	for(int i=0;i<n;i++){
		Send(res[i]);
	}
}

Bruno

#include "Bruno.h"
#include "bits/stdc++.h"
using namespace std;

void Bruno(int n, int l, vector<int> a) {
	vector<int> res, tot;
	int x = 0;
	for(int j=0;j<20;j++) x |= (a[j] << j);
	a.erase(a.begin(), a.begin() + 20);
	for(int i=0;i<n;i++){
		if(a[i]) tot.push_back(i);
	}
	auto add = [&](int l, int r){
		for(int i=l;i<=r;i++){
			//~ cout<<i<<endl;
			Remove(i);
		}
	};
	
	int lx = 0;
	if(x){
		add(0, tot[0] - 1);
		for(int i=1;i<x;i+=2){
			add(tot[i-1] + 1, tot[i] - 1);
			add(tot[i] + 1, tot[i+1] - 1);
			Remove(tot[i]);
			Remove(tot[i+1]);
		} Remove(tot[0]);
		lx = tot[x - 1] + 1;
	} 
	
	tot.erase(tot.begin(), tot.begin() + x);
	reverse(tot.begin(), tot.end());
	if(!tot.empty()){
		add(tot[0] + 1, n - 1);
		for(int i=1;i<(int)tot.size();i+=2){
			add(tot[i] + 1, tot[i-1] - 1);
			add(tot[i+1] + 1, tot[i] - 1);
			Remove(tot[i]);
			Remove(tot[i+1]);
		} Remove(tot[0]);
		add(lx, tot.back() - 1);
	} else add(lx, n - 1);
	
	
}

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