Submission #1214156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214156		thelegendary08	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	36 ms	6460 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i < n; i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vb vector<bool>
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(x) cout<<x<<' '<<#x<<'\n';
using namespace std;

namespace {

// int variable_example = 0;

}

void Anna(int N, std::vector<char> S) {
	vi v;
	int d = -1;
	f0r(i, N){
		if(S[i] == 'X'){
			v.pb(1); d = i; break;
		}
		else v.pb(0);
	}
	if(d != -1){
		if(d != N-1)v.pb(0);
		for(int i = d + 2; i<N; i++){
			if(S[i] == 'Z' && (i == N-1 || S[i+1] != 'Z')){
				v.pb(1);
			}
			else v.pb(0);
		}
	}
	// vout(v);
	vector<long long>fib;
	fib.pb(1);
	fib.pb(2);
	for(int i=0; i<61;i++){
		fib.pb(fib[fib.size() - 1] + fib[fib.size() - 2]);
	}
	for(int i = 0; i<N; i+=63){
		long long cur = 0;
		for(int j = i; j<min(i+63, N); j++){
			if(v[j] == 1){
				cur += fib[j - i];
			}
		}
		// dout(cur);
		for(int j = 0; j<44; j++){
			if((1LL << j) & cur){
				Send(1);
			}
			else Send(0);
		}
	}
	
	
	
	return;
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i < n; i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vb vector<bool>
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vpii vector<pair<int,int>>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';

using namespace std;

namespace {

// int variable_example = 0;

// int FunctionExample(int P) { return 1 - P; }

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
	vi v;
	vector<long long>fib;
	fib.pb(1);
	fib.pb(2);
	for(int i=0; i<61;i++){
		fib.pb(fib[fib.size() - 1] + fib[fib.size() - 2]);
	}
	// vout(A);
	for(int i = 0; i<L; i+=44){
		long long int cur = 0;
		for(int j = i; j<i+44; j++){
			cur += (1LL << (j-i)) * A[j];
		}
		// dout(cur);
		int ptr = 62; 
		vi w;
		while(ptr >= 0){
			if(fib[ptr] > cur){
				w.pb(0); ptr--;
			}
			else{
				if(ptr == 0){
					w.pb(1); ptr--;
				}
				else{
					w.pb(1); w.pb(0); cur -= fib[ptr]; ptr-=2;
				}
			}
		}
		reverse(w.begin(), w.end());
		for(auto u : w)v.pb(u);
	}
	// vout(v);
	vb vis(N);
	int fi = -1;
	f0r(i, N){
		if(v[i] == 0){
			Remove(i); vis[i] = 1;
		}
		else{
			fi = i;
			break;
		}
	}
	// cout<<fi<<'\n';
	if(fi != -1){
		vi os;
		os.pb(fi);
		for(int i = fi + 1; i<N; i++){
			if(v[i] == 1)os.pb(i);
		}
		// vout(os);
		for(int i = 1; i<os.size(); i++){
			for(int j = os[i]-1; j>os[i-1]; j--){
				if(!vis[j]){
					// dout(j);
					Remove(j); vis[j] = 1;
				}
			}
			if(!vis[os[i]]){
				// dout(os[i]);
				Remove(os[i]); vis[os[i]] = 1;
			}
		}
		for(int i = N-1; i > os.back(); i--){
			// dout(i);
			Remove(i);
		}
		// dout(fi);
		Remove(fi);
	}
	
	/*
	vi v;
	for(int i = 0; i<2 * N; i+=2){
		if(A[i] + A[i+1] == 0)v.pb(0);
		else if(A[i] + A[i+1] == 1)v.pb(1);
		else v.pb(2);
	}
	
	vi a,b,c;
	f0r(i, N){
		if(v[i] == 0)a.pb(i);
		else if(v[i] == 1)b.pb(i);
		else c.pb(i);
	}
	
	vi ma(a.size(), -1);
	int p1 = 0; int p2 = 0;
	while(p1 < a.size()){
		while(p2 < b.size() && b[p2] < a[p1])p2++;
		if(p2 != b.size()){
			ma[p1] = p2;
		}
		p1++;
	}
	
	vi mb(b.size(), -1);
	p1 = 0; p2 = 0;
	while(p1 < b.size()){
		while(p2 < c.size() && c[p2] < b[p1])p2++;
		if(p2 != c.size())mb[p1] = p2;
		p1++;
	}
	vout(ma); 
	vout(mb);
	vector<pair<pii,int>> ranges;
	f0r(i, a.size()){
		if(ma[i] != -1 && mb[ma[i]] != -1)ranges.pb(mp(mp(c[mb[ma[i]]], a[i]), b[ma[i]]));
	}
	
	sort(ranges.begin(), ranges.end());
	vb vis(N);
	int ce = -1;
	f0r(i, ranges.size()){
		cout<<ranges[i].first.second<<' '<<ranges[i].second<<' '<<ranges[i].first.first<<'\n';
		if(ranges[i].first.second > ce){
			FOR(j, ranges[i].first.second + 1, ranges[i].second){
				if(!vis[j]){
					Remove(j); vis[j] = 1;
				}
			}
			FOR(j, ranges[i].second + 1, ranges[i].first.first){
				if(!vis[j]){
					Remove(j); vis[j] = 1;
				}
			}
			Remove(ranges[i].second);
			vis[ranges[i].second] = 1;
			ce = ranges[i].first.first;
		}
	}
	f0r(i, N){
		if(!vis[i])Remove(i);
	}
	*/
}

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