Submission #882687

#	Time	Username	Problem	Language	Result	Execution time	Memory
882687		gustavo_d	cmp (balkan11_cmp)	C++17	100 / 100	1136 ms	107064 KiB

cmp

// https://oj.uz/problem/view/balkan11_cmp > p151
#include "cmp.h"
#include <bits/stdc++.h>
using namespace std;

int modifiers[6];

void remember(int n) {
	int idx = 1;
    for (int i=0; i<6; i++) {
		modifiers[i] = idx;
		int pref = n >> 2*(5-i); // pref de len i+1
		bit_set(pref+idx);
		//if (n == 2991) cout << pref << ' ' << idx << endl;
		idx += pow(4, i+1);
	}
}

int compare(int b) {
	int prefs[7]; prefs[0] = 0;
	for (int i=0; i<6; i++) {
		int pref = b >> 2*(5-i); // pref de len i+1
		prefs[i+1] = pref;
	}
	int l = 1; int r = 6;
	int lcp = 0;
	//cout << "====" << endl;
	while (l <= r) {
		int m = (l + r) / 2;
		if (bit_get(prefs[m] + modifiers[m-1])) {
			// = prefs, can be lcp
			//if (b==3542) cout << prefs[m] << ' ' << m << endl;
			lcp = m;
			l = m+1;
		} else r = m-1;
	}
	if (lcp == 6) {
		// all prefixes are equal
		return 0;
	} else {
		// compare prefixes ending at lcp+1
		int num_of_b_after_lcp = prefs[lcp+1] - prefs[lcp] * 4; // index in lcp+1 é a +, 4^lcp
		if (num_of_b_after_lcp == 1) {
			// check if in a is 0 (a is smaller)
			if (bit_get(prefs[lcp+1]-1+modifiers[lcp])) return 1;
			else return -1;
		} else if (num_of_b_after_lcp == 2) {
			// check if in a is 3 (a is bigger)
			if (bit_get(prefs[lcp+1]+1+modifiers[lcp])) return -1;
			else return 1;
		}
		else if (num_of_b_after_lcp == 0) return -1;
		else return 1;
	}
}

• Subtask 1: 100 / 100