답안 #660857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660857 2022-11-23T10:51:38 Z 600Mihnea 비교 (balkan11_cmp) C++17
46 / 100
1480 ms 104932 KB
#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

**/
# 결과 실행 시간 메모리 Grader output
1 Partially correct 1480 ms 104932 KB Output is partially correct - maxAccess = 16, score = 46