Submission #523082

#	Time	Username	Problem	Language	Result	Execution time	Memory
523082		amunduzbaev	Ancient Machine (JOI21_ancient_machine)	C++17	0 / 100	54 ms	11044 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;
			}
		}
	}
	
	if(tmp.size() <= tt.size()){
		for(auto x : tt) res[x] = 1;
		Send(0);
	} else {
		for(auto x : tmp) res[x] = 1;
		Send(1);
	}
	
	//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
	//~ cout<<endl;
	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 is = a[0]; 
	a.erase(a.begin(), a.begin() + 1);
	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);
		}
	};
	if((int)tot.size() >= 3){
		assert((int)tot.size()&1);
		if(!is){
			add(0, tot[0] - 1);
			int last = tot[0];
			for(int i=1;i<(int)tot.size();i+=2){
				add(last + 1, tot[i] - 1);
				add(tot[i] + 1, tot[i+1] - 1);
				Remove(tot[i]);
				//~ cout<<tot[i]<<endl;
				Remove(tot[i+1]);
				//~ cout<<tot[i+1]<<endl;
				last = tot[i+1];
			}
			Remove(tot[0]);
			//~ cout<<tot[0]<<endl;
			add(last + 1, n - 1);
		} else {
			reverse(tot.begin(), tot.end());
			add(tot[0] + 1, n - 1);
			int last = tot[0];
			for(int i=1;i<(int)tot.size();i+=2){
				add(tot[i] + 1, last - 1);
				add(tot[i+1] + 1, tot[i] - 1);
				Remove(tot[i]);
				Remove(tot[i+1]);
				last = tot[i+1];
			} Remove(tot[0]);
			add(0, last - 1);
		}
	} else {
		add(0, n - 1);
	}
}

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