제출 #660857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660857		600Mihnea	비교 (balkan11_cmp)	C++17	46 / 100	1480 ms	104932 KiB

cmp

#include "cmp.h"

#include <bits/stdc++.h>

using namespace std;

void remember(int n)
{
  int v = 1;
  for (int bit = 11; bit >= 0; bit--)
  {
    v = 2 * v + !!(n & (1 << bit));
    bit_set(v);
  }
}

/**

if a != b => at least one bit in which code(a) is set and code(b) is not set

a < b => code(a) < code(b)
a = b => code(a) = code(b)

compar niste numere cu ac numar de biti

if a < b => a e o submultime a lu b

1 0 0 0 0 1 1 1
0 0 1 1 1 1 0 0


log3(a) + 2 * log3(b)


0 1 2
e 0 => verific daca e 0


**/

int compare(int n)
{
  int L = 0, R = 11, sol = 0;
  while (L <= R)
  {
    int bit = (L + R) / 2;
    int v = 1;
    for (int j = 11; j >= bit; j--)
    {
      v = 2 * v + !!(n & (1 << j));
    }
    if (bit_get(v) == 1)
    {
      R = bit - 1;
    }
    else
    {
      if (n & (1 << bit))
      {
        sol = +1;
      }
      else
      {
        sol = -1;
      }
      L = bit + 1;
    }
  }
  return sol;
}

/**

6 + 2 * 6 = 18

**/

• Subtask 1: 46 / 100