Japanese Olympiad in Informatics Spring Camp 2017

device.cpp

// Ivan Carvalho
// City - JOI SC 2017
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
 
static vector<int> sequencia;
 
static void build_sequence(){
 
	const long double factor = 1.055645;
 
	sequencia.push_back(0);
	sequencia.push_back(1);
 
	for(int i = 2;i<256;i++){
		int x = int( factor*sequencia.back() );
		if(x == sequencia.back()) x += 1;
		sequencia.push_back(x);
	}
 
}
 
void InitDevice(){
	
	build_sequence();
 
}
 
static void Magic(long long X, int &ini, int& fim ){
 
	ini = 0;
	fim = 0;
 
	long long temp = (X >> 20);
	fim = sequencia[temp];
 
	X -= (temp)*(1 << 20);
	ini += X;
	fim += ini;
 
}
 
int Answer(long long S, long long T){
 
	if(S == T) return 2;
 
	int inia,fima,inib,fimb;
 
	Magic(S,inia,fima);
	Magic(T,inib,fimb);
 
	if(inia <= inib && inib <= fima) return 1;
	if(inib <= inia && inia <= fimb) return 0;
 
	return 2;
 
}

encoder.cpp

// Ivan Carvalho
// City - JOI SC 2017
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 250010;
 
typedef long long ll;
typedef pair<int,int> ii;
 
static vector<int> grafo[MAXN],sequencia;
static int ini[MAXN],idx[MAXN],dfsCount;
 
static void build_sequence(){
 
	const long double factor = 1.055645;
 
	sequencia.push_back(0);
	sequencia.push_back(1);
 
	for(int i = 2;i<256;i++){
		int x = int( factor*sequencia.back() );
		if(x == sequencia.back()) x += 1;
		sequencia.push_back(x);
	}
 
}
 
static void dfs(int v,int p){
 
	ini[v] = ++dfsCount;
 
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs(u,v);
	}
 
	int lo = 0, hi = 255, mid, ans = -1;
 
	while(lo <= hi){
		mid = (lo + hi)/2;
		if(ini[v] + sequencia[mid] >= dfsCount){
			ans = mid;
			hi = mid - 1;
		}
		else{
			lo = mid + 1;
		}
	}
 
	idx[v] = ans;
	dfsCount = ini[v] + sequencia[ans];
 
}
 
static long long coding(int A,int B){
 
	long long davez = A;
	davez += (1LL << 20)*ll(B);
 
	return davez;
 
}
 
void Encode(int N, int A[], int B[]){
 
	build_sequence();
 
	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}
 
	dfs(0,-1);
 
	for(int i = 0;i<N;i++){
		ini[i]--;
	}
 
	for (int i = 0; i < N; ++i) {
		Code(i, coding(ini[i],idx[i]) );
	}
 
}