Submission #119728

#	Time	Username	Problem	Language	Result	Execution time	Memory
119728		kureyo	cmp (balkan11_cmp)	C++11	100 / 100	1804 ms	82780 KiB

cmp

#include "cmp.h"

void bit_set_(int x) {
  bit_set(x + 1);
}

int bit_get_(int x) {
  return bit_get(x + 1);
}

void remember(int value) {
  bit_set_(value >> 6);
  bit_set_(64 + ((value >> 9) & 7));
  bit_set_(80 + ((value >> 3) & 7));
  bit_set_(88 + ((value >> 0) & 7));
}

int compare_three(int value, int bit) {
  // [higher 6 bit (64)] + [ 11~9 (8) ] + [not used(8)]  + [ 5~3 (8) ] + [ 2~0 (8) ]
  int interest = (value >> (bit - 2)) & (bit == 8 ? 63 : 7);
  int query_basis = 64 + (11 - bit) / 3 * 8;
  if (bit == 8) query_basis = 0;

  if (bit_get_(query_basis + interest)) {
    if (bit >= 3) {
      return compare_three(value, bit - 3);
    } else {
      return 0;
    }
  }

  if (interest & 4) {
    // look upper
    while ((interest & 7) != 7) {
      interest++;
      if (bit_get_(query_basis + interest)) {
        return -1; // b < a
      }
    }
    return 1;
  } else {
    // look lower
    while ((interest & 7) != 0) {
      interest--;
      if (bit_get_(query_basis + interest)) {
        return 1; // b > a
      }
    }
    return -1;
  }
}

int compare(int value) {
  int upper_half = value >> 6;
  if (bit_get_(upper_half)) {
    return compare_three(value, 5);
  }
  return compare_three(value, 11);
}

• Subtask 1: 100 / 100