답안 #119728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119728 2019-06-22T03:41:22 Z kureyo 비교 (balkan11_cmp) C++11
100 / 100
1804 ms 82780 KB
#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);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1804 ms 82780 KB Output is correct - maxAccess = 10, score = 100